Hey, I think the time complexity should be E ^ d where d is the maximum number of outgoing flights from a particular airport. Squaring it means that the max is 2 only
In a dense graph where every vertices is connected to every vertices . Let us assume it is o(v*e) and we know e == v-1 right cause it is a dense graph..... we can write(v * (v-1)) thus it will be v2 -v // eliminating v we get v2 it can also be called as e2
@@penolove15 see e is different in different cases This is implemented using adjacency list In v+e -> e is edges . A list of edge. One vertex will only have one list of edges right? But using matrix e is the edge (singular). So we definitely know there will be v-1 edges. This question might be bugging you why e is different in different cases. Cause if we use adjacency list then it is not a sign of dense graph. What is dense graph? It is a graph where every nodes is connected to every node. So there might be some vertex which do not have any neighbors. There might be some vertex which is only connected to one neighbor . So e is the list of edges and there will only be 1 list of edges for one vertex . So to get more tighter time complexity.
from collections import defaultdict from typing import List class Solution: def findItinerary(self, tickets: List[List[str]]) -> List[str]: adj = defaultdict(list) tickets.sort(reverse=True)
for src, dest in tickets: adj[src].append(dest) res = [] def dfs(src):
while adj[src]: next_dest = adj[src].pop() dfs(next_dest) res.append(src) dfs("JFK")
Not sure if this is simpler, obviously more efficient but coming up with res.append(src) after the while loop and then do res[::-1] last is so subtle. I would simply try to do res.append(src) in the beginning of the recursive function and then not do the reverse at the end. That is incorrect though. Not sure if I would be able to remember that in interview..
Hi, I wanted to thank you as I learnt a lot of approaches and problem solving skills from you. Yesterday I got a 100% hike at my company because of this. Keep up the good work brother!
Small optimization I noticed: instead of popping a val from adj[src], we can instead set it to -1 prior to dfs then return it to its normal value afterwards. Then, during our loop we can check if a val is -1 and continue if it is.
Iterate over a copy of the collection because you never want to modify something that you're iterating over... That sir is a gem and could literally be the most useful bit of non-basic knowledge I've ever heard anyone say over a RUclips channel
I like that this solution is not like the perfect 5 line submissions in leetcode. It's a well thought out solution that has intuition embedded in it. You're the man!
I did it a different way using heaps + toposort. Was quite efficient (faster than 98% for Python) and more intuitive for me. class Solution: # weighted lexicographic cost (first char has most weight, second has second-most, etc.) def calc_lex(self, string): return sum([(ord(c) * ((3 - i)**((3 - i) + (3 - i)))) for i, c in enumerate(string)]) # push to min heap based on calculated lex cost, and pop from heap when topo sorting # topo sort doesn't like cycles, so you're deleting the edges as you go along # when a base case is reached, it backtracks and adds the vals to the result def findItinerary(self, tickets: List[List[str]]) -> List[str]: adj, weights = {}, {} for src, dst, in tickets: if src not in adj: adj[src] = [] weights[src] = self.calc_lex(src) if dst not in adj: adj[dst] = [] weights[dst] = self.calc_lex(dst) heapq.heappush(adj[src], (weights[dst], dst)) print(adj) topo = [] def topsort(root, adj): if not root: return
while adj[root]: cost, nei = heapq.heappop(adj[root]) topsort(nei, adj) nonlocal topo topo.append(root) return topsort('JFK', adj) topo.reverse() return topo
I was initially going for this solution but I implemented toposort wrong but definitely agree that this is more intuitive for me, too! The problem is easily put in the task scheduling category at the first look. Thanks for sharing the solution as well!
cutting an array from middle and again inserting from middle increases the time complexity i think! so you can assign adj[src][i]="*" and if v=="*" continue; it will save some time; But problem solving approach was very nice!
Hi, if the solution provided in the video failed, maybe you can refer to the solution below using Hierholzer’s Algorithm: class Solution: def findItinerary(self, tickets: List[List[str]]) -> List[str]: adj = collections.defaultdict(list) res = [] for dep,dst in tickets: heapq.heappush(adj[dep],dst)
I have the same issue. The editorial of leetcode also mentioned that the solution would get Time Limit Exceeded. I guess leetcode either added a few new test cases or made the time more strict.
@@dhruvgovil4270 class Solution: def findItinerary(self, tickets: List[List[str]]) -> List[str]: adj = {src: [] for src, dst in tickets} res = [] for src, dst in tickets: adj[src].append(dst) for key in adj: adj[key].sort() def dfs(adj, result, src): if src in adj: destinations = adj[src][:] while destinations: dest = destinations[0] adj[src].pop(0) dfs(adj, res, dest) destinations = adj[src][:] res.append(src) dfs(adj, res, "JFK") res.reverse() if len(res) != len(tickets) + 1: return [] return res
Hmm, I couldn't pass time limit using DFS approach, then I have to learn Heirholzer's algorithm for finding Eulerian path ;). Thank you for keep me motivated
Same, i got tle on the final test case. Seems like the final test case was added later because a lot of solutions that we accepted earlier are now failing
Did it today and I could still pass the new test with DFS by using a check to not try duplicate tickets twice at the same depth, as in if you are at "AAA" on step 20 and there's multiple un-used tickets from "AAA" to "BBB" and you've tried one of them and failed you don't try the rest on the same step.
My understanding of Time complexity: In normal DFS: Every node is visited once, so TC = (1+e1) + (1+e2)+....+(1+en) => V+E Here, Every node is visited n number of times based on number of incoming edges. so TC = (1+e1)*ea + (1+e1)*eb + ...+ (1+en)*ezp => E + E^2 => E^2
I was asked to solve similar problem but harder. Problem was instead of tickets, a friend told you his itinerary, however some airports didn’t exist when you checked and some others have no connections, so you decided to reconstruct the itinerary with the lowest edit distance for airports that didn’t exist with a valid route. So you have a list or map of valid airports and valid connections between airports and a list with the itinerary starting and returning to the same city. Some airports in the itinerary have errors in the letters and some others are wrong because it was impossible to flight from a city to another.
A possible way to solve the TLE issue is using a dict to store the count of flight ticket. It aviods the list insertion operation which is O(n). The main logic reminds the same. class Solution: def findItinerary(self, tickets: List[List[str]]) -> List[str]: adjList = {} self.ticketSize = len(tickets) path = [] for pair in tickets: start = pair[0] dest = pair[1] if start not in adjList: adjList[start] = {dest:1} else: if dest not in adjList[start]: adjList[start][dest] = 1 else: adjList[start][dest] += 1
for key in adjList: adjList[key] = dict(sorted(adjList[key].items(), key=lambda item: item[0])) def traverse(cur):
if self.ticketSize == 0: return True elif cur not in adjList: return False for nextStop in adjList[cur].keys(): if adjList[cur][nextStop] > 0: adjList[cur][nextStop] -= 1 self.ticketSize -= 1 path.append(nextStop) if travese(nextStop): return True adjList[cur][nextStop] += 1 self.ticketSize += 1 path.pop(-1) return False
Can you explain why is the code now on your website different from the video ? Why is there no need to add back the tickets into the adjacency list after popping it. Video code runs into time limit exceeded. Thank you !
The trickiest part for me is knowing to add the insert and pop after the call to dfs(), because that is not "standard" depth first search. I believe that 's a customized dfs, which is hard to know when & where to implement. Is there a name for this approach, or is it essentially just a form of backtracking ?
Thanks for the video. A quick observation: I only sorted the input by destination (2nd value) rather then the first value as you suggested. And I'm still passing all test cases, not sure why.
I have a fundamental question: In which scenarios do we need to pop the added values in visited nodes or del the values once visited? I see some cases we don't remove from the visit, while in some we do.
@@jayeshnagarkar7131 I think it's we don't wanna visit the same edge again, that's why we pop it from adj list, otherwise we'd just use a visited set if we just wanna keep track of visited nodes
Really great work um working hard to finish all your videos and it is really beneficial.But I have a question for you sir or for people who will see this comment. what after I have learnt programming basics and algorithms and datastructure and solved many problems,.can I apply for a job or is there something else I have to learn . Thanks in advance.
Actually, there is no need to store adj[src] into temp. I remember Neetcode said in the stack problems, it is just a snapshot, so if we change adj[src] below. It won't change in the for loop.
can someone please explain why are we removing(temporarily) airports/neighbors from an adjacency list of a vertex? why did we not bother to keep a visited set?I mean i know there will be cycles in graph, but is this(the one shown) the way to avoid them? not sure im following, can someone please chime in?
I would never be able to come up with this solution. I got Time limit error with your solution, but passed with this solution that I have found in the solutions tab: graph = defaultdict(list)
for src, dset in sorted(tickets, reverse=True): graph[src].append(dset)
res = [] def dfs(src): while graph[src]: dfs(graph[src].pop()) res.append(src)
Neetcode had said the reason. For instance, number of V is much less than number of E, then V + E gonna be taken as E. if there are double directed, we should traverse the edges twice. So it is gonna be E ^ 2, technically, it should be (V + E) ^ 2
@@danielsun716 I started to grab a sense of idea what they mean... it's vaguely like in the most outer dfs : each edge out of E in total can route back to the same node which will invoke a nested dfs. Inside this nested dfs, we have at most E edges and again each edge can route back to this same node, then invoke a nested nested dfs so on and so forth...That's where the d(max outdegree of a node) came from I think imo, but I think both E^2 and E^d are very abstract estimate TC, the real exact TC perhaps we'll never figure it out, it's too complex for me lmao
I look at it this way. Let's say you go from JFK to another node (which has JFK in their adjacency list), you will repeat the _whole_ DFS process for JFK again, which makes it a recursive approach. In vanilla DFS, such recursion is avoided by breaking based on a visit set, but in this problem, we don't do that. So the time complexity becomes - O(time taken for a DFS)^2. Let me know if that clarifies the issue.
Can anybody explain how the time complexity is O((V+E)^2) ? I'm quite a bit confused on it, any ideas on how to visualize time complexity for this algorithm would be really helpful. Thanks!
The way you solved it, actually does not demonstrate, why it is marked as a hard problem. At best it is a medium. There is a secret to it, making it a hard problem.
adj[src].pop(i) and adj[src].insert(i, v) is not O(1) operation. the time comlexity is O(len(adj[src])). In my solution, i optimized this by marking adj[src][i] as '' empty string, same purpose ``` class Solution: def findItinerary(self, tickets: List[List[str]]) -> List[str]: adj = {} self.getGraph(adj, tickets) path = [] ans = [] self.dfs('JFK', adj, path, len(tickets) + 1, ans) return ans[0] def dfs(self, node, adj, path, length, ans): # base case if ans: return # recursive rule path.append(node) if len(path) == length: if not ans: ans.append(path.copy()) return neis = adj.get(node, []) for i, nei in enumerate(neis): if nei: ori = neis[i] neis[i] = '' # mark the path as visited self.dfs(nei, adj, path, length, ans) neis[i] = ori path.pop() def getGraph(self, adj, tickets): for t in tickets: src, end = t if src in adj: adj.get(src).append(end) else: neis = [end] adj[src] = neis for k, v in adj.items(): v.sort() ```
I think there is a better solution here. You don't need to 'undo' all your work if the brute force dfs shows it doesn't complete the itinerary. Instead you go down the brute force path, but you just keep track of where you had an opportunity to fork. It turns out that whenever you do this, the graphs that are left are loops and guaranteed to bring you right back to where the fork began. As for sorting, I just chose assemble the adjacency list as a minHeap. Here is my code so you can see the approach. ' ' ' from collections import defaultdict from heapq import * class Solution: def findItinerary(self, tickets: List[List[str]]) -> List[str]: srcMap = defaultdict(list) for src, dst in tickets: heappush(srcMap[src], dst) def fly(src): path = list() forks = list() # greedy until you hit a dead end # keep track of forks as you go while srcMap[src]: dst = heappop(srcMap[src]) if (srcMap[src]): forks.insert(0, (len(path), src)) path.append(dst) src = dst # resolve forks for loc, src in forks: sideTrip = fly(src) while sideTrip: path.insert(loc, sideTrip.pop()) return path itinerary = ['JFK'] itinerary.extend( fly('JFK') ) return itinerary ' ' '
pls correct me if Im wrong for the TC analysis... But for those who get O(E^d), does it mean sth. like below procedure: in the most outer dfs : each edge out of E in total can route back to the same node which will invoke a nested dfs. Inside this nested dfs, we have at most E edges and again each edge can route back to this same node, then invoke a nested nested dfs so on and so forth...Is this where the d(max outdegree of a node) came from? If so, then I have a follow-up doubt: Consider inside the inner-most nested (which should be the d'th nested?) dfs, now the max-outdegree node is "popped" (since no out-degrees now), but among roughly E edges/choices, we could still choose an arbitrary one as the base/pivot node, and from now on every nested dfs would be invoked because of the new base/pivot node... what I'm trying to say is, O(E^d) is not really accurate imho? Or I'm so dumb and somewhere goes wrong above during the thought process? anybody has any thoughts on this??? It's really challenging for me lmao, I'd rather just choose the Eulerian way to solve this if this shows up in my coding interview
class Solution: can someone explain to me on why this is working even without the temp variable? def findItinerary(self, tickets: List[List[str]]) -> List[str]: adj = {} tickets.sort() for ticket in tickets: departure, arrival = ticket if departure not in adj: adj[departure] = [] adj[departure].append(arrival) res = ["JFK"] def dfs(src): if len(res) == len(tickets) + 1: return True if src not in adj: return False for i, v in enumerate(adj[src]): adj[src].pop(i) res.append(v) if dfs(v): return True adj[src].insert(i,v) res.pop() return False dfs("JFK") return res
Follow this if you have TLE issue: Note: you can use defaultdict(deque) instead of defaultdict(list) so that you don't need to sort in reverse order and use popleft() function instead. class Solution: def findItinerary(self, tickets: List[List[str]]) -> List[str]:
# create an adjacency list for each airport and the list of airports reachable from that airport adj_list = {} for src, dst in tickets: if src not in adj_list: adj_list[src] = [] adj_list[src].append(dst) # sort the list of reachable airports in reversed so that it maintains lexi order when pop # and popping from the last element is less costly than from the first element for src in adj_list.keys(): adj_list[src].sort(reverse=True) stack = [] stack.append("JFK") result = [] # start from JFK and keep adding the next child till we reach the last airport to the top of the stack # if we reach the airport from where we can't travel further, pop it from the stack and add it to result # our result will have the reversed answer (end of trip -> beginning of trip) while stack: src_airport = stack[-1] if src_airport in adj_list and len(adj_list[src_airport]) > 0: stack.append(adj_list[src_airport].pop()) else: result.append(stack.pop()) return result[::-1]
This solution was getting TLE so I looked into solutions and someone knows why this works? from collections import defaultdict class Solution: def findItinerary(self, tickets: list[list[str]]) -> list[str]: tickets.sort(reverse=True) adj = defaultdict(list) res = [] for f, t in tickets: adj[f].append(t) def dfs(node:str): while adj[node]: dfs(adj[node].pop()) res.append(node) dfs("JFK") res.reverse() return res
Hey, I think the time complexity should be E ^ d where d is the maximum number of outgoing flights from a particular airport. Squaring it means that the max is 2 only
yeah, I had the same thought!
So in the worst case d would be V right? In that case we can state that as O(E^V)
In a dense graph where every vertices is connected to every vertices . Let us assume it is o(v*e) and we know e == v-1
right cause it is a dense graph.....
we can write(v * (v-1))
thus it will be v2 -v // eliminating v we get v2 it can also be called as e2
@@anmolkarki5248 so why the complexity will be v * e not v ^ e?
@@penolove15 see e is different in different cases
This is implemented using adjacency list
In v+e -> e is edges . A list of edge.
One vertex will only have one list of edges right?
But using matrix e is the edge (singular).
So we definitely know there will be v-1 edges.
This question might be bugging you why e is different in different cases.
Cause if we use adjacency list then it is not a sign of dense graph.
What is dense graph?
It is a graph where every nodes is connected to every node.
So there might be some vertex which do not have any neighbors.
There might be some vertex which is only connected to one neighbor .
So e is the list of edges and there will only be 1 list of edges for one vertex .
So to get more tighter time complexity.
There is a new test case(number 80) that causes this solution to go over the time limit
Yep, this one hurt. I thought I had the problem solved and there came test 80.
from collections import defaultdict
from typing import List
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
adj = defaultdict(list)
tickets.sort(reverse=True)
for src, dest in tickets:
adj[src].append(dest)
res = []
def dfs(src):
while adj[src]:
next_dest = adj[src].pop()
dfs(next_dest)
res.append(src)
dfs("JFK")
return res[::-1]
@@mohammadrafi895 🐐
@@mohammadrafi895 Dude this is a much simpler solution than the neetcode one. Hope it gets more upvotes.
Not sure if this is simpler, obviously more efficient but coming up with res.append(src) after the while loop and then do res[::-1] last is so subtle.
I would simply try to do res.append(src) in the beginning of the recursive function and then not do the reverse at the end. That is incorrect though.
Not sure if I would be able to remember that in interview..
Hi, I wanted to thank you as I learnt a lot of approaches and problem solving skills from you. Yesterday I got a 100% hike at my company because of this.
Keep up the good work brother!
That's awesome to hear! Congrats!!!
Small optimization I noticed: instead of popping a val from adj[src], we can instead set it to -1 prior to dfs then return it to its normal value afterwards. Then, during our loop we can check if a val is -1 and continue if it is.
The Best Leetcode solver on RUclips!! I got a job because of how I learn how to approach problem by watching your videos! Thank you so much!!
Iterate over a copy of the collection because you never want to modify something that you're iterating over... That sir is a gem and could literally be the most useful bit of non-basic knowledge I've ever heard anyone say over a RUclips channel
yeah, thank you for mentioning that. I think it is a good point to remember
💡 GRAPH PLAYLIST: ruclips.net/video/EgI5nU9etnU/видео.html
I like that this solution is not like the perfect 5 line submissions in leetcode. It's a well thought out solution that has intuition embedded in it. You're the man!
now this approach will TIMEOUT. one optimization to pass the tests is to explore DISTINCT destinations, another is to use the Hierholzer's
I did it a different way using heaps + toposort. Was quite efficient (faster than 98% for Python) and more intuitive for me.
class Solution:
# weighted lexicographic cost (first char has most weight, second has second-most, etc.)
def calc_lex(self, string):
return sum([(ord(c) * ((3 - i)**((3 - i) + (3 - i)))) for i, c in enumerate(string)])
# push to min heap based on calculated lex cost, and pop from heap when topo sorting
# topo sort doesn't like cycles, so you're deleting the edges as you go along
# when a base case is reached, it backtracks and adds the vals to the result
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
adj, weights = {}, {}
for src, dst, in tickets:
if src not in adj:
adj[src] = []
weights[src] = self.calc_lex(src)
if dst not in adj:
adj[dst] = []
weights[dst] = self.calc_lex(dst)
heapq.heappush(adj[src], (weights[dst], dst))
print(adj)
topo = []
def topsort(root, adj):
if not root:
return
while adj[root]:
cost, nei = heapq.heappop(adj[root])
topsort(nei, adj)
nonlocal topo
topo.append(root)
return
topsort('JFK', adj)
topo.reverse()
return topo
I was initially going for this solution but I implemented toposort wrong but definitely agree that this is more intuitive for me, too! The problem is easily put in the task scheduling category at the first look. Thanks for sharing the solution as well!
pop(i) the sailor man
Lol
cutting an array from middle and again inserting from middle increases the time complexity i think! so you can assign adj[src][i]="*" and if v=="*" continue; it will save some time; But problem solving approach was very nice!
But then if it's not removed. Those stars will be searched again later which again will contribute to time complexity. So it's same
Hi, if the solution provided in the video failed, maybe you can refer to the solution below using Hierholzer’s Algorithm:
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
adj = collections.defaultdict(list)
res = []
for dep,dst in tickets:
heapq.heappush(adj[dep],dst)
def dfs(dep):
while adj[dep]:
stop = heapq.heappop(adj[dep])
dfs(stop)
res.append(dep)
dfs('JFK')
return res[::-1]
Anyone else getting a time limit exceeded result with this solution? Doesn't pass the 80th Test case for me
True.
I have the same issue. The editorial of leetcode also mentioned that the solution would get Time Limit Exceeded. I guess leetcode either added a few new test cases or made the time more strict.
Same
Use an adjacency list of a set instead of list
So that removal and insertion is O(1)
@@felixboachieyiadom4457but then how would u traverse alphabetically?
This approach is giving TLE right now, to solve this question we have to use Hierholzer's Algorithm
Ok, but who is flying from SFO to SJC, that is 34 miles LOL
depends on traffic jam, you might get faster by flying
Taylor Swift in her private jet
Code is not submitting on leetcode , time limit is getting exceeded
You can find the updated solution on the neetcode website
@@ilovenaturesound5123 couldn't find
@@dhruvgovil4270
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
adj = {src: [] for src, dst in tickets}
res = []
for src, dst in tickets:
adj[src].append(dst)
for key in adj:
adj[key].sort()
def dfs(adj, result, src):
if src in adj:
destinations = adj[src][:]
while destinations:
dest = destinations[0]
adj[src].pop(0)
dfs(adj, res, dest)
destinations = adj[src][:]
res.append(src)
dfs(adj, res, "JFK")
res.reverse()
if len(res) != len(tickets) + 1:
return []
return res
Hmm, I couldn't pass time limit using DFS approach, then I have to learn Heirholzer's algorithm for finding Eulerian path ;). Thank you for keep me motivated
Same, i got tle on the final test case. Seems like the final test case was added later because a lot of solutions that we accepted earlier are now failing
Did it today and I could still pass the new test with DFS by using a check to not try duplicate tickets twice at the same depth, as in if you are at "AAA" on step 20 and there's multiple un-used tickets from "AAA" to "BBB" and you've tried one of them and failed you don't try the rest on the same step.
@@joelbolkert4273 could you share your answer please?
@@joelbolkert4273 could u share your code
The last TC on leetcode gives a TLE for this
My understanding of Time complexity:
In normal DFS:
Every node is visited once, so
TC = (1+e1) + (1+e2)+....+(1+en) => V+E
Here,
Every node is visited n number of times based on number of incoming edges. so
TC = (1+e1)*ea + (1+e1)*eb + ...+ (1+en)*ezp => E + E^2 => E^2
they added new testcase and this solution is giving TLE now
bactracking is not allowed anymore, you need to come up with a Hierholzer's algorithm
@@name_surname_1337 Not true, you can use same approach just skip failed duplicate destinations on your current backtrack path.
@@guyhadas4887 Until they add another testcase, lol
I was asked to solve similar problem but harder. Problem was instead of tickets, a friend told you his itinerary, however some airports didn’t exist when you checked and some others have no connections, so you decided to reconstruct the itinerary with the lowest edit distance for airports that didn’t exist with a valid route.
So you have a list or map of valid airports and valid connections between airports and a list with the itinerary starting and returning to the same city. Some airports in the itinerary have errors in the letters and some others are wrong because it was impossible to flight from a city to another.
For which company?
2024 this solution is timing out now
A possible way to solve the TLE issue is using a dict to store the count of flight ticket. It aviods the list insertion operation which is O(n). The main logic reminds the same.
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
adjList = {}
self.ticketSize = len(tickets)
path = []
for pair in tickets:
start = pair[0]
dest = pair[1]
if start not in adjList:
adjList[start] = {dest:1}
else:
if dest not in adjList[start]:
adjList[start][dest] = 1
else:
adjList[start][dest] += 1
for key in adjList:
adjList[key] = dict(sorted(adjList[key].items(), key=lambda item: item[0]))
def traverse(cur):
if self.ticketSize == 0:
return True
elif cur not in adjList:
return False
for nextStop in adjList[cur].keys():
if adjList[cur][nextStop] > 0:
adjList[cur][nextStop] -= 1
self.ticketSize -= 1
path.append(nextStop)
if travese(nextStop):
return True
adjList[cur][nextStop] += 1
self.ticketSize += 1
path.pop(-1)
return False
path.append("JFK")
travese("JFK")
return path
Can you explain why is the code now on your website different from the video ? Why is there no need to add back the tickets into the adjacency list after popping it.
Video code runs into time limit exceeded.
Thank you !
we can optimize backtracking's pop/push in for loop by using linked list data structure
Thanks for the explanation. However, this code exceeds the time limit (gives TLE).
This kind of question makes me wanna throw acid in my eyes but for some reason i wanna keep doing. I guess im a mascochist.
line 3 can be replaced with adj = collections.defaultdict(list)
The trickiest part for me is knowing to add the insert and pop after the call to dfs(), because that is not "standard" depth first search. I believe that 's a customized dfs, which is hard to know when & where to implement. Is there a name for this approach, or is it essentially just a form of backtracking ?
Cannot pass all test cases for naive solution using DFS+Backtracking?
Make room for the elephant, Topological sort! :)
Thanks for the video. A quick observation: I only sorted the input by destination (2nd value) rather then the first value as you suggested. And I'm still passing all test cases, not sure why.
only in hashmap ordered, so sorted 2nd value can ensure it
The code solution you have on your website doesn’t pass anymore, time limit exceeded
This solution doesn't work, it fails the 80st test case.
DFS Solution times out so implement it using stack to get it through LC
I have a fundamental question: In which scenarios do we need to pop the added values in visited nodes or del the values once visited? I see some cases we don't remove from the visit, while in some we do.
we do not want to visit the same node again thats why we pop it
@@jayeshnagarkar7131 I think it's we don't wanna visit the same edge again, that's why we pop it from adj list, otherwise we'd just use a visited set if we just wanna keep track of visited nodes
Great Explanation. Thank you!
Thanks!
Really great work um working hard to finish all your videos and it is really beneficial.But I have a question for you sir or for people who will see this comment.
what after I have learnt programming basics and algorithms and datastructure and solved many problems,.can I apply for a job or is there something else I have to learn .
Thanks in advance.
Awesome explanation
I was hoping to get visual depiction of post order DFS and linear complexity algorithm, assuming sorted input. 😀
Anyway, top notch content! Thanks!
Shouldn't the time complexity be D^E (where D is max number of outgoing flights from a given airport)
Excellent! Would you help to explain Euler trail in a directed graph, which is Hierholzer's algorithm ?
You may find this helpful. Euler trail explanation: ruclips.net/video/8MpoO2zA2l4/видео.html
You don't need to do all that
Just go through each city in order. Submitted with just 12 short lines
u are a god bro.
Neetcode getting political this video by writing ACAB ;)
lol i didnt notice that
Actually, there is no need to store adj[src] into temp. I remember Neetcode said in the stack problems, it is just a snapshot, so if we change adj[src] below. It won't change in the for loop.
hey can kahn's topological sort be used in this problem ?
No, Kahn needs to be on an acyclic graph, the problem contains cycles.
What if we do Topological ordering of Edges instead of vertices? In this way we visit each edge exactly once AND in order...?
can someone please explain why are we removing(temporarily) airports/neighbors from an adjacency list of a vertex? why did we not bother to keep a visited set?I mean i know there will be cycles in graph, but is this(the one shown) the way to avoid them? not sure im following, can someone please chime in?
I would never be able to come up with this solution. I got Time limit error with your solution, but passed with this solution that I have found in the solutions tab:
graph = defaultdict(list)
for src, dset in sorted(tickets, reverse=True):
graph[src].append(dset)
res = []
def dfs(src):
while graph[src]:
dfs(graph[src].pop())
res.append(src)
dfs("JFK")
return res[::-1]
Can you explain why it's O(V + E)^2?
Neetcode had said the reason. For instance, number of V is much less than number of E, then V + E gonna be taken as E. if there are double directed, we should traverse the edges twice. So it is gonna be E ^ 2, technically, it should be (V + E) ^ 2
@@danielsun716 take a look at the pinned comment which states tc = E^V, I haven't figured it out yet;-; do you got it why so?
@@chaoluncai4300 so do I. I still think it should be (v + e) ^ 2
@@danielsun716 I started to grab a sense of idea what they mean... it's vaguely like in the most outer dfs : each edge out of E in total can route back to the same node which will invoke a nested dfs. Inside this nested dfs, we have at most E edges and again each edge can route back to this same node, then invoke a nested nested dfs so on and so forth...That's where the d(max outdegree of a node) came from I think imo, but I think both E^2 and E^d are very abstract estimate TC, the real exact TC perhaps we'll never figure it out, it's too complex for me lmao
great explanation, thanks! could someone please explain why when len(route) == len(tickets) + 1 we have definitely reached our result?
Hi! Can anyone explain more why the time complexity for backtracking is the square of (V + E)?
I look at it this way. Let's say you go from JFK to another node (which has JFK in their adjacency list), you will repeat the _whole_ DFS process for JFK again, which makes it a recursive approach.
In vanilla DFS, such recursion is avoided by breaking based on a visit set, but in this problem, we don't do that.
So the time complexity becomes - O(time taken for a DFS)^2. Let me know if that clarifies the issue.
@@arkamukherjee457 shoudnt it be E^d then where d is max outgoing edges?
Can anybody explain how the time complexity is O((V+E)^2) ? I'm quite a bit confused on it, any ideas on how to visualize time complexity for this algorithm would be really helpful.
Thanks!
Great explanation!
The way you solved it, actually does not demonstrate, why it is marked as a hard problem. At best it is a medium. There is a secret to it, making it a hard problem.
Shouldn't the time complexity be (num_of_tickets)!? Since we have n empty slots in itenary which need to be filled with n tickets..
why if dfs(): return True can stop the function call
adj[src].pop(i) and adj[src].insert(i, v) is not O(1) operation. the time comlexity is O(len(adj[src])). In my solution, i optimized this by marking adj[src][i] as '' empty string, same purpose
```
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
adj = {}
self.getGraph(adj, tickets)
path = []
ans = []
self.dfs('JFK', adj, path, len(tickets) + 1, ans)
return ans[0]
def dfs(self, node, adj, path, length, ans):
# base case
if ans:
return
# recursive rule
path.append(node)
if len(path) == length:
if not ans:
ans.append(path.copy())
return
neis = adj.get(node, [])
for i, nei in enumerate(neis):
if nei:
ori = neis[i]
neis[i] = '' # mark the path as visited
self.dfs(nei, adj, path, length, ans)
neis[i] = ori
path.pop()
def getGraph(self, adj, tickets):
for t in tickets:
src, end = t
if src in adj:
adj.get(src).append(end)
else:
neis = [end]
adj[src] = neis
for k, v in adj.items():
v.sort()
```
can you do 370? It is a great question I believe.
I think Eulerian path solution is correct for this instead of backtracking and exploring all possible options.
class Solution {
// Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
public List findItinerary(List tickets) {
HashMap graph = buildMap(tickets);
LinkedList currentPath = new LinkedList();
dfs(graph, "JFK", tickets.size() + 1, currentPath);
return new ArrayList(currentPath);
}
private void dfs(HashMap graph, String source, int count, LinkedList currentPath) {
if(count == currentPath.size()) {
return;
}
PriorityQueue target = graph.get(source);
while(target !=null && !target.isEmpty()) {
String next = target.poll();
dfs(graph, next, count, currentPath);
}
currentPath.addFirst(source);
}
private HashMap buildMap(List tickets) {
HashMap map = new HashMap();
for(List list : tickets) {
String source = list.get(0);
String target = list.get(1);
if(map.containsKey(source)) {
map.get(source).offer(target);
} else {
PriorityQueue ls = new PriorityQueue();
ls.offer(target);
map.put(source, ls);
}
}
return map;
}
}
why you took if len(res) == len(tickets)+1 as base case, can you explain pls?
I think there is a better solution here. You don't need to 'undo' all your work if the brute force dfs shows it doesn't complete the itinerary.
Instead you go down the brute force path, but you just keep track of where you had an opportunity to fork. It turns out that whenever you do this, the graphs that are left are loops and guaranteed to bring you right back to where the fork began.
As for sorting, I just chose assemble the adjacency list as a minHeap.
Here is my code so you can see the approach.
' ' '
from collections import defaultdict
from heapq import *
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
srcMap = defaultdict(list)
for src, dst in tickets:
heappush(srcMap[src], dst)
def fly(src):
path = list()
forks = list()
# greedy until you hit a dead end
# keep track of forks as you go
while srcMap[src]:
dst = heappop(srcMap[src])
if (srcMap[src]):
forks.insert(0, (len(path), src))
path.append(dst)
src = dst
# resolve forks
for loc, src in forks:
sideTrip = fly(src)
while sideTrip:
path.insert(loc, sideTrip.pop())
return path
itinerary = ['JFK']
itinerary.extend( fly('JFK') )
return itinerary
' ' '
Please make a video on Leetcode 355 - Design Twitter please.
Wouldn't popping and inserting into the adjacency array, within the for loop of dfs, increase the runtime by another factor of n?
yes so the time complexity should be E^2 * N where N is the number of airports.
Why we start from JFK ? can we start from other node? I checked its failing.
The problem statement itself says that you must start at JFK
Use Hierholzer's algorithm
I was wondering what impact we can have here if we allow self loops ?
ion think it'll matter, just'll be counted as a regular outgoing edge
backtracking is naive, use eulerian circuit
best
pls correct me if Im wrong for the TC analysis... But for those who get O(E^d), does it mean sth. like below procedure: in the most outer dfs : each edge out of E in total can route back to the same node which will invoke a nested dfs. Inside this nested dfs, we have at most E edges and again each edge can route back to this same node, then invoke a nested nested dfs so on and so forth...Is this where the d(max outdegree of a node) came from? If so, then I have a follow-up doubt: Consider inside the inner-most nested (which should be the d'th nested?) dfs, now the max-outdegree node is "popped" (since no out-degrees now), but among roughly E edges/choices, we could still choose an arbitrary one as the base/pivot node, and from now on every nested dfs would be invoked because of the new base/pivot node... what I'm trying to say is, O(E^d) is not really accurate imho? Or I'm so dumb and somewhere goes wrong above during the thought process? anybody has any thoughts on this??? It's really challenging for me lmao, I'd rather just choose the Eulerian way to solve this if this shows up in my coding interview
Clearly confirm it wasn't 'doable' for me.
How do we know we should use DFS and not BFS
BFS using for finding shortest path, DFS for finding all paths and compare with some if statements
you don't need temp
This is not working anymore , its giving TLE
class Solution:
can someone explain to me on why this is working even without the temp variable?
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
adj = {}
tickets.sort()
for ticket in tickets:
departure, arrival = ticket
if departure not in adj:
adj[departure] = []
adj[departure].append(arrival)
res = ["JFK"]
def dfs(src):
if len(res) == len(tickets) + 1:
return True
if src not in adj:
return False
for i, v in enumerate(adj[src]):
adj[src].pop(i)
res.append(v)
if dfs(v):
return True
adj[src].insert(i,v)
res.pop()
return False
dfs("JFK")
return res
I did not understand the time complexity
doesnt it return the path？
This looks like a heap problem
How is this a hard problem?
Follow this if you have TLE issue:
Note: you can use defaultdict(deque) instead of defaultdict(list) so that you don't need to sort in reverse order and use popleft() function instead.
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
# create an adjacency list for each airport and the list of airports reachable from that airport
adj_list = {}
for src, dst in tickets:
if src not in adj_list:
adj_list[src] = []
adj_list[src].append(dst)
# sort the list of reachable airports in reversed so that it maintains lexi order when pop
# and popping from the last element is less costly than from the first element
for src in adj_list.keys():
adj_list[src].sort(reverse=True)
stack = []
stack.append("JFK")
result = []
# start from JFK and keep adding the next child till we reach the last airport to the top of the stack
# if we reach the airport from where we can't travel further, pop it from the stack and add it to result
# our result will have the reversed answer (end of trip -> beginning of trip)
while stack:
src_airport = stack[-1]
if src_airport in adj_list and len(adj_list[src_airport]) > 0:
stack.append(adj_list[src_airport].pop())
else:
result.append(stack.pop())
return result[::-1]
Java Code without causing a Time limit Exceeded in Leetcode
class Solution {
public List findItinerary(List tickets) {
LinkedList iternary = new LinkedList();
Map graph = new HashMap();
Stack stack = new Stack();
stack.push("JFK");
for(List ticket : tickets){
graph.computeIfAbsent(ticket.get(0), k->new PriorityQueue());
graph.get(ticket.get(0)).add(ticket.get(1));
}
while(!stack.isEmpty()){
String destination = stack.peek();
if(!graph.getOrDefault(destination, new PriorityQueue()).isEmpty()){
stack.push(graph.get(destination).poll());
}
else{
iternary.addFirst(stack.pop());
}
}
return iternary;
}
}
This solution was getting TLE so I looked into solutions and someone knows why this works?
from collections import defaultdict
class Solution:
def findItinerary(self, tickets: list[list[str]]) -> list[str]:
tickets.sort(reverse=True)
adj = defaultdict(list)
res = []
for f, t in tickets:
adj[f].append(t)
def dfs(node:str):
while adj[node]:
dfs(adj[node].pop())
res.append(node)
dfs("JFK")
res.reverse()
return res
collections.defaultdict(list) bro, come on