Reconstruct Itinerary - Leetcode 332 - Python

0:00 - Understand the problem
4:00 - Drawing Explanation
11:49 - Coding Explanation

leetcode 332

#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[teechin]

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

[AbsAnubis]

There is a new test case(number 80) that causes this solution to go over the time limit

[premraja]

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!

[ThomasKatz]

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.

[kimstuart]

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 YouTube channel

[shadreyes]

The Best Leetcode solver on Youtube!! I got a job because of how I learn how to approach problem by watching your videos! Thank you so much!!

[jacobli]

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 =
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]

[redblacktech]

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!

[chenjieY-zq]

now this approach will TIMEOUT. one optimization to pass the tests is to explore DISTINCT destinations, another is to use the Hierholzer's

[ThePacemaker]

Anyone else getting a time limit exceeded result with this solution? Doesn't pass the 80th Test case for me

[DanielRodrigues-bxlr]

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

[rahatsshowcase]

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!

[AnupKumar-ymqz]

Code is not submitting on leetcode, time limit is getting exceeded

[roshatron]

This approach is giving TLE right now, to solve this question we have to use Hierholzer's Algorithm

[jshpro]

Ok, but who is flying from SFO to SJC, that is 34 miles LOL

[IK-xkex]

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

[bluesteel]

The last TC on leetcode gives a TLE for this

[Chirayu]

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

[thunderstorm-dc]

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

[faingtoku]

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.