LeetCode Patterns: Reconstruct Itinerary (#332)

0:00 Let me set up a scenario for you. I'm going to hand you exactly three plane tickets. You have one ticket from JFK to KUL. Okay, I'm checking. You have a second ticket from JFK to NRT, and you have a third ticket from NRT back to JFK. You're holding these three tickets in your hand. You are physically standing at JFK. Which flight do you instinctively want to take first? Well, if we're playing by the rules of standard algorithmic tiebreakers, we want the lexically smallest route. So, I mean, I'm looking at my two options out of JFK, which are KUL and NRT.

0:35 Right. And, you know, K comes before N in the alphabet, so my brain instantly just says, hand the gate agent the ticket to KUL. Exactly. That is exactly what my brain does too. But let's actually play that out. The moment you take that flight, what happens? Well, you land at KUL. And you step off the plane. Yeah. You look at the departure board, and you realize you are entirely stranded. Right, because there are zero tickets in my hand that depart from KUL. None. You are stuck at KUL. And worse, you still have two unused tickets sitting in your pocket.

1:06 The one from JFK to NRT, and the one from NRT back to JFK. Oh, yeah. So you haven't just taken a bad route. You've actually failed the core requirement of the trip. Exactly. Because the actual correct itinerary for those three tickets is JFK to NRT back to JFK and then finally to KUL. And, you know, that tiny trap, that incredibly reasonable instinct to just greedily pick the alphabetical next step and accidentally maroon yourself, it really tells you everything you need to know about why this specific problem trips up so many experienced engineers.

1:38 So, you're given a list of airline tickets. You must start your journey at JFK. If there are multiple valid ways to use the tickets, you must return the lexically, meaning alphabetically, smallest valid route. Right. But here is the massive flashing neon sign that dictates the entire underlying math. You must use every single ticket exactly once. I really want to highlight that for you. The goal is to use every ticket exactly once. It is not visit every airport. Precisely. That single rule changes the entire landscape.

2:13 Have you ever played that puzzle game as a kid where you have to draw a shape on a piece of paper like a house with an X inside it without ever lifting your pen? Oh, yeah. And without ever tracing over the same line twice, right? Exactly. You know how you always end up stuffing a corner if you start at the wrong roof point? Yeah. It's incredibly frustrating. Well, in computer science and graph theory, tracing over every line exactly once is called an Eulerian path. Because the rule here is to consume every flight exactly once.

2:40 This isn't a standard generic search problem where airports are the primary focus. That's an edge problem. Right. This is a specialized Eulerian path construction problem. The center of gravity here is the flights, not the cities. Okay. I hear you on the Eulerian path concept. But let's be honest about what happens in a real coding interview when you first read those constraints. Because I know what my brain does, and it's what almost every engineer's brain does. You reach for backtracking. Yes.

3:07 You see a starting point. You see an adjacent C list of choices for where to go next. So you instinctively reach for the most familiar tool in your belt, brute force backtracking. It is the most natural instinct in the world. You look at the graph and think, okay, I'll pick an alphabetical destination. I'll recursively try to build a route. And if I hit a dead end before I've used all my tickets, I'll just backtrack. Undo the choice. Right. Yeah. I'll undo that choice, give myself the ticket back, and try the next hallway.

3:33 And that literal brute force trial and error solution does technically work. But I'm going to defend that instinct for a second. Yeah. Backtracking feels incredibly safe. How so? It feels safe because it's explicit. You are in total control of the choice, the undo, and the recovery path. To me, it feels like walking into a massive, dark maze with a giant ball of string. You take a turn, and if you hit a wall, you just reel the string back in. Reel it right back to the fork in the road. Exactly. And in programming terms, reeling that string back in is just popping frames off your call stack.

4:10 It feels like the correct way to do a search. It's a great analogy, and here is the fundamental rebuttal to the ball of string. That feeling of control is actually just unnecessary, heavy bookkeeping. Unnecessary. Completely. When you do that, you are actively maintaining used edge states. You're constantly restoring tickets to your pool, and you're manually validating routes. You're treating the maze like a total mystery. Ah, I see. You're solving a much more general problem than you actually need to.

4:36 Because of that flashing neon sign we mentioned earlier, the promise that a perfect path exists using every ticket. Exactly. The graph inherently knows how its sub-roads snap together. When a problem guarantees that an Eulerian path exists, there is a mathematical certainty built into the structure. So you don't need all the explicit trial and error ceremony. Yeah. You can let the graph do the heavy lifting. I also want to quickly touch on another false lens people bring to this. They see places, and they see directional dependencies between them.

5:08 So the brain immediately jumps to topological sort. Oh, yeah. That's a common one. But topological sort strictly assumes acyclic dependencies, meaning no loops. And flight itineraries definitely have loops. Happily and frequently. You fly out of JFK, you loop through a few cities, and you fly back to JFK. Topological sort just fundamentally breaks down the absolute second a cycle appears. So we had to throw that tool out entirely. Okay. So topological sort is out because of the loops. And left to right backtracking is out because it's overly heavy and ignores the inherent mathematical structure of the graph.

5:45 We need a new mental model. A complete paradigm shift. Right. Because if I shouldn't be asking my algorithm, what is the smartest next airport to fly to, what question should I be asking? What's fascinating here is that the most important question to ask is actually about permanence. You should be asking, when is an airport's position in my final itinerary permanently fixed? Wait, what do you mean permanently fixed? If I'm traversing a graph, isn't my current position fixed as soon as I decide to travel there?

6:14 No, and that's the left to right bias talking. The answer to when an airport's position is finalized is surprisingly late. How late? An airport's position in your route is fixed only when you reach it, and there are absolutely zero unused outgoing tickets left from that specific airport. Zero outgoing tickets. It's so dead end. But wait, how is hitting a dead end a good thing? If I get stuck in an airport with no tickets leaving it, doesn't that mean my algorithm completely failed? I mean, that is exactly the scenario backtracking tries to actively avoid.

6:44 And that is the brilliance of this algorithm. You have to reframe what stuck means. If the problem guarantees a valid route exists and you followed a path until you literally cannot take another step out of a city, that dead end isn't a mistake. Okay. At that exact moment, that airport must belong at the very end of whatever suffix of the route you are currently finishing. You can't extend the route past it. So its job and the final answer is completely settled. Okay. I want to use a tactile analogy for this because it helps me visualize it.

7:14 Imagine you are pulling a single continuous physical thread through every ticket exactly once. Every time you follow an unused flight, you extend the thread further into the maze. I like this. When you hit an airport that has no more flights leaving, it's not a failure. It's just the moment you can't extend the thread anymore. So what do you do? You tie off that end. That node is done. That is a perfect visualization. You literally tie it off. In computer science terminology, what we are describing is Eulerian post-order construction.

7:46 Post-order, meaning we do the recording work after we've explored the paths on the way back up the call stack. Exactly. You aren't writing the route down while you move forward. You are writing it down while you retreat. Wow. You aggressively exhaust all outgoing edges first, taking the lexically smallest one available, and only when you are completely stuck do you record the airport. Which means the very first dead end you hit is the absolute final airport in your entire journey. Yes. The first dead end is your first certainty.

8:17 Let's go back to your opening trap JFK to KUL, JFK to NRT, and NRT to JFK. Let's trace it with this new rule. Okay, let's do it. You start at JFK. You have choice. Lexical order tells you to consume the edge to KUL first. So you fly JFK to KUL. Yep. You land at KUL. Now, you look for outgoing tickets. There are zero. You are stuck. So under the backtracking mindset, I would panic and undo. But under this post-order mindset, I say, great, I found the end of the thread. I tie off KUL. I record it in my list.

8:48 Exactly. KUL is recorded first. Now, what does the call stack do? It retreats. It unwinds to the airport that brought you there, which was JFK. Okay. I am virtually back at JFK. I look at my tickets. I still have an unused ticket from JFK to NRT. Right. So you haven't exhausted JFK yet. You take the unused ticket to NRT. I am at NRT. I have one ticket leaving here, which goes back to JFK. I take it. Now you are at JFK again. You look at your tickets. There are no unused tickets leaving JFK. You are fully exhausted.

9:16 So I tie off JFK. My recorded list is now KUL and then JFK. I unwind my call stack back to NRT. NRT has no tickets left. Yeah. Tie off NRT. I unwind back to the starting JFK. No tickets left. I tie off JFK. So your recorded list, in order of tying them off, is KUL, then JFK, then NRT, then JFK. And because we recorded this backward from the end of the journey to the beginning, I just reduced that final array, which gives me JFK to NRT, back to JFK to KUL. The exact perfect itinerary. We hit the trap, but the unwind fixed it for us.

9:53 Exactly. You consume the edges on the way down, but you finalize the vertices on the way back up. Okay. Tracing that backward for three tickets is a really neat trick. But here is where my brain starts sweating. Real flight routes aren't just one straight string. How does this handle complex, nested flight paths? Like, the official leak code example for this problem features a nasty side cycle. Well, the Atlanta cycle. Yeah. You have a main route, but halfway through, you take a random loop through ATL and back.

10:22 Right. Cycles inside of cycles. When I see that, I feel this impending dread of having to write custom merge logic. I start thinking, okay, I found a cycle. I need to keep track of array indices. I need to figure out where the loop began and cleanly splice this side trip into the middle of my main array so the route doesn't break. And that dread is exactly why this algorithm, which provides the intuition for what's known as the Hierholzer algorithm, is so deeply beautiful. It handles all of that seamlessly.

10:51 Really? No index tracking? None at all. Let's take that exact cycle example and walk the graph slowly so we can really see the mechanics. Let's do it. Imagine your tickets dictate this specific path. You leave JFK and you take a flight to ATL. Okay. I am physically in Atlanta. One ticket burned. From ACL, you have a ticket back to JFK. You take it. Got it. So we just did a mini loop. We are back exactly where we started, but those first two tickets are consumed. Now from JFK, you take your next ticket over to SFO.

11:22 Right. Flying cross country. I am in San Francisco. From SFO, you take a ticket back to ATL. Okay. Back in Atlanta for the second time. And finally from ATL, you take a ticket back to SFO. You land at SFO for the second time. And now there are zero unused tickets left in the entire graph. Okay. Let me track this. So the sequence of flights we just physically took was JFK to ATL to JFK to SFO to ATL to SFO. And at that second SFO, we hit our ultimate dead end. The thread cannot be pulled any further.

11:53 Right. So following our rule, that last SFO is the first airport that becomes final. We tie it off. We append it to our list. SFO is in the list. Now we unwind the call stack. We retreat to the airport that brought us there, which was the second ATL. ATL has no unused tickets left either. So ATL becomes final. We append it. So our list is SFO, then ATL. We retreat again. We retreat to the first SFO. It's exhausted. So we append it. Then we retreat to the middle JFK. Append it. Retreat to the first ATL.

12:21 Append it. Retreat to the starting JFK. Append it. Okay. Wait, let me look at the recorded list. SFO, ATL, SFO, JFK, ATL, JFK. If I reverse that final list. Well, wait, I can't say dot, dot, dot. But if I reverse it, I get JFK, ATL, JFK, SFO, ATL, SFO. That is the exact flawlessly merged ITL itinerary. What stands out to you the most about that unwinding process? Honestly, what stands out is what we didn't do. I never wrote a single line of code to manually splice that cycle. I didn't keep track of a single array index.

12:58 I didn't write an if statement looking for a loop. Because you don't have to. You only commit an airport to the final list once all the work below it is completely finished. Wow. Think about what that means for a cycle. If you are on a main path and you accidentally stumble into a massive complicated side loop, your main path simply pauses. It just waits. It waits for the inner cycle to exhaust itself, hit a dead end, and append all its nodes during its own unwind. By the time your main path finally resumes and appends its own airport, the entire nested side cycle has already been perfectly laid out behind it.

13:33 So the side cycles just automatically snap into their perfect place during the unwind. That is the Heerholzer algorithm. That's the core intuition of it, yes. Finding Eulerian circuits by letting subtours naturally merge themselves on the backtrack. That is incredibly elegant. It feels almost like magic the first time you trace it. Right. But, okay, let's bring this back down to the reality of passing a coding interview. Sure. We have the conceptual graph structure mapped out. We know we are recording on the unwind.

14:01 But we still have that very specific requirement from the lexical tiebreaker. Right. Alphabetical order. If there are multiple valid itiner AAs, we need the alphabetically smallest one. How do we satisfy that without ruining the elegance of the post-order unwind? This really raises an important question about software design. The separation of concerns. You have to separate your graph invariant, which is the rule of when to record an airport from your adjacency container, which dictates how you store and retrieve your tickets.

14:33 Okay. Let me jump in here with a massive warning for anyone listening, because this is where I see people fall into a huge trap. They hear lexically smallest, and they summarize this whole deep dive as, oh, I get it. Just greebly pick the smallest airport next. That is such a dangerous oversimplification. If you just say, greedily pick the smallest airport, it sounds like lexical order alone is solving the problem. It absolutely is not. Right. The lexical order only has one specific job. It decides which edge to consume next when you have multiple valid tickets leaving your current airport.

15:06 That's it. It's just a tiebreaker for the traversal order. Exactly. The actual validity of the route, the mathematical guarantee that you won't get permanently stranded early, like in our opening trap, comes strictly from the Eulerian edge exhaustion and the post-order unwind process. Consume edges in lexical order, but finalize vertices in exhaustion order. So practically speaking, how do we implement this adjacency container? We need a data structure that hands us the lexically smallest ticket, but does it fast.

15:35 Because sorting a list of destinations every single time we enter a node would be an absolute nightmare for performance. Precisely. If you are coding this in Python, there is a fantastic, elegant trick. Before you build your graph, you sort all your tickets in reverse alphabetical order up front. Reverse alphabetical? Wait, why? Think about how Python lists work. You build your adjacency list, mapping each departure airport to a list of its destinations. Because you sort it in reverse first, the destinations are sitting in the list with the lexically smallest airport at the very end of the array.

16:09 Oh, I see. If the smallest airport is at the end of the array, I don't have to shift any elements around. Right. When I need the next destination, I just call pop on the list. Exactly. Popping from the end of a list in Python is an O of 1 operation. It pulls the smallest airport off instantly and simultaneously removes the edge from the graph so you can't use it again, fast and clean. And what if I'm writing this in Java? In Java, the standard and most readable approach is to use a priority queue for each departure airport's list of destinations.

16:40 Okay, a priority queue. Yeah. As you load the tickets into the priority queue, they naturally and efficiently order themselves. When you pull the queue, you get the lexically smallest destination in logarithmic time. And again, it cleanly removes the edge for you. Quick edge case question. What about duplicate tickets? What if I literally have two physically identical tickets from JFK to SFO in my input array? You treat them as completely distinct edges. Do not try to deduplicate them using a set or any clever grouping.

17:10 Because it's about the tickets, not the destination. Exactly. Remember, this problem is strictly edge-centric. If you have two physical tickets, you must fly that exact route twice. Your priority queue or your Python list will just hold two identical string entries and you will pop them one by one. Got it. And I think we need to explicitly remind everyone that the final reversal of your appended list is not just some optional cosmetic cleanup step. No, it is a mandatory mechanism of the algorithm.

17:38 If you ever forget why you are reversing the array at the end, you have probably lost your grip on the core invariant of the algorithm. Think of the thread. Exactly. Remember the physical thread. You tied off the dead ends first. The absolute last airport in your physical trip was the very first one written down in your array. Reversing it at the end is what actually reconstructs the forward flow of time. So what does this all mean when we zoom out? We came into this deep dive looking at LeetCode 332.

18:04 On the surface, it looks like a simple depth-first search or a standard backtracking maze task. But it's actually a masterclass in pattern recognition. It really is. Once you recognize that Eulerian smell, that specific mandate to use every edge exactly, once the solution collapses from a massive state management headache into a sleek two-step dance. Descend and unwind. Descend through the graph by consuming the smallest edge and unwind by recording the exhausted airport. And this edge-centric pattern applies so widely.

18:36 We cover broader graph patterns and how to spot them in our algorithms for any software engineer series. Definitely check that out. And you'll absolutely see this exact post-order mechanism pop up in adjacent exact match problems like valid arrangement of pairs. But for now, just mastering this one shift in perspective is a huge level up. I completely agree. Pull the thread, hit the dead end, and tie it off. We'll catch you on the next deep dive.