6:00 - 6:40 you ignore the queue when you're talking about the space. Actually, asymptotically if the resultant list is O(n) in W.C it seems there's no need to mention the space needed for the queue. but anyway, if we still want to say something about space needed for queue..what can we say? In terms of the queue, when the tree is a linkedlist, it's actually best case scenario because the queue will contain at most once child at every stage. so O(1) space needed for queue. for the queue the W.C is when we have full symmetric tree? then it will be O(2^h) memory needed for the queue (all nodes at last level?)
Thank you for the clear explanation!! Can you make a video about the problem 332. Reconstruct Itinerary? I'm quite confused about Hierholzer's Algorithm approach.
Quite frankly I'm not planning on making one because I know it's been covered plenty out there already. I'll post my solution down below here for you because I think it will be mostly understandable as-is -- I did it the DFS way btw; it's going to be a cold day in hell before I try to approach it with Hierzoler's algo: class Solution: def findItinerary(self, tickets): adjList = defaultdict(list) for frm, dest in tickets: adjList[frm].append(dest) visited = {} for frm in adjList: adjList[frm].sort() visited[frm] = [False for _ in range(len(adjList[frm]))] def dfs(start, curr): nonlocal result if len(curr) == len(tickets) + 1: result = list(curr) return True elif start not in adjList: return False for i, dest in enumerate(adjList[start]): if not visited[start][i]: visited[start][i] = True curr.append(dest) isPossible = dfs(dest, curr) visited[start][i] = False curr.pop() if isPossible: return True return False result = [] dfs("JFK", ["JFK"]) return result
This is super weird... testing the code by hitting the “Run Code ^” button first works... but then when I hit “Submit” it gives me the following AttributeError: “NoneType” object has no attribute ‘val’
Sounds to me like there's a test case failing where you're trying to access a node's `val` property... however, the node is Null! Did you include error checking at the start to ensure the test case isn't an empty tree? :)
6:00 - 6:40
you ignore the queue when you're talking about the space.
Actually, asymptotically if the resultant list is O(n) in W.C it seems there's no need to mention the space needed for the queue.
but anyway, if we still want to say something about space needed for queue..what can we say?
In terms of the queue, when the tree is a linkedlist, it's actually best case scenario because the queue will contain at most once child at every stage. so O(1) space needed for queue.
for the queue the W.C is when we have full symmetric tree? then it will be O(2^h) memory needed for the queue (all nodes at last level?)
Thank you for the clear explanation!! Can you make a video about the problem 332. Reconstruct Itinerary? I'm quite confused about Hierholzer's Algorithm approach.
Quite frankly I'm not planning on making one because I know it's been covered plenty out there already. I'll post my solution down below here for you because I think it will be mostly understandable as-is -- I did it the DFS way btw; it's going to be a cold day in hell before I try to approach it with Hierzoler's algo:
class Solution:
def findItinerary(self, tickets):
adjList = defaultdict(list)
for frm, dest in tickets:
adjList[frm].append(dest)
visited = {}
for frm in adjList:
adjList[frm].sort()
visited[frm] = [False for _ in range(len(adjList[frm]))]
def dfs(start, curr):
nonlocal result
if len(curr) == len(tickets) + 1:
result = list(curr)
return True
elif start not in adjList:
return False
for i, dest in enumerate(adjList[start]):
if not visited[start][i]:
visited[start][i] = True
curr.append(dest)
isPossible = dfs(dest, curr)
visited[start][i] = False
curr.pop()
if isPossible:
return True
return False
result = []
dfs("JFK", ["JFK"])
return result
awesome man! Keep it up :)
Ty ty! will do :)
This is super weird... testing the code by hitting the “Run Code ^” button first works... but then when I hit “Submit” it gives me the following AttributeError: “NoneType” object has no attribute ‘val’
Sounds to me like there's a test case failing where you're trying to access a node's `val` property... however, the node is Null! Did you include error checking at the start to ensure the test case isn't an empty tree? :)