Reconstruct Itinerary - Practice Coding Problems

Reconstruct Itinerary - Problem

You are given a list of airline tickets where tickets[i] = [from_i, to_i] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Input & Output

Example 1 — Basic Circuit

$ Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

› Output: ["JFK","MUC","LHR","SFO","SJC"]

💡 Note: Start from JFK, follow tickets: JFK → MUC → LHR → SFO → SJC. This uses all tickets exactly once.

Example 2 — Multiple Valid Paths

$ Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

› Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]

💡 Note: Multiple valid itineraries exist, but we return the lexicographically smallest one.

Example 3 — Simple Round Trip

$ Input: tickets = [["JFK","KUL"],["KUL","JFK"]]

› Output: ["JFK","KUL","JFK"]

💡 Note: Simple round trip: JFK → KUL → JFK using both tickets.

Constraints

1 ≤ tickets.length ≤ 300
tickets[i].length == 2
from_i.length == 3
to_i.length == 3
from_i and to_i consist of uppercase English letters
from_i ≠ to_i

Visualization

Tap to expand

Understanding the Visualization

Input

List of airline tickets as directed edges

Process

Build graph and find path using all edges exactly once

Output

Lexicographically smallest valid itinerary starting from JFK

Key Takeaway

🎯 Key Insight: This is an Eulerian path problem - use Hierholzer's algorithm for optimal solution

Asked in

G Google 42 a Amazon 35 f Facebook 28 M Microsoft 24

This is an Eulerian path problem where we need to visit every edge (ticket) exactly once. The optimal approach uses Hierholzer's algorithm with DFS and sorted adjacency lists to ensure lexical ordering. Time: O(V + E), Space: O(V + E).

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Backtracking	O(V + E)²	O(V + E)	Build graph and use DFS with backtracking to find valid itinerary
Brute Force with Permutations	O(n!)	O(n)	Generate all possible ticket arrangements and find the lexicographically smallest valid itinerary
Hierholzer's Algorithm (Eulerian Path)	O(V + E)	O(V + E)	Use Hierholzer's algorithm to find Eulerian path that visits every edge exactly once

DFS with Backtracking — Algorithm Steps

Build adjacency list from tickets
Sort destinations for each airport lexicographically
Use DFS with backtracking starting from JFK
Try each destination and backtrack if path fails

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Create adjacency list from tickets and sort destinations

DFS Search

Use DFS to explore paths, backtrack when stuck

Valid Path

Find path that uses all tickets exactly once

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_TICKETS 300
#define MAX_AIRPORTS 100
#define MAX_LEN 4

char airports[MAX_AIRPORTS][MAX_LEN];
int airportCount = 0;
int graph[MAX_AIRPORTS][MAX_AIRPORTS];
int used[MAX_TICKETS];
char result[MAX_TICKETS + 1][MAX_LEN];
int resultSize = 0;

int findAirport(char* airport) {
    for (int i = 0; i < airportCount; i++) {
        if (strcmp(airports[i], airport) == 0) return i;
    }
    strcpy(airports[airportCount], airport);
    return airportCount++;
}

void dfs(int airport, char tickets[][2][MAX_LEN], int ticketsSize) {
    for (int i = 0; i < ticketsSize; i++) {
        if (!used[i]) {
            int from = findAirport(tickets[i][0]);
            if (from == airport) {
                used[i] = 1;
                int to = findAirport(tickets[i][1]);
                dfs(to, tickets, ticketsSize);
            }
        }
    }
    strcpy(result[resultSize++], airports[airport]);
}

char** solution(char tickets[][2][MAX_LEN], int ticketsSize, int* returnSize) {
    memset(used, 0, sizeof(used));
    resultSize = 0;
    airportCount = 0;
    
    int jfk = findAirport("JFK");
    dfs(jfk, tickets, ticketsSize);
    
    // Reverse result
    for (int i = 0; i < resultSize / 2; i++) {
        char temp[MAX_LEN];
        strcpy(temp, result[i]);
        strcpy(result[i], result[resultSize - 1 - i]);
        strcpy(result[resultSize - 1 - i], temp);
    }
    
    *returnSize = resultSize;
    char** returnArray = malloc(resultSize * sizeof(char*));
    for (int i = 0; i < resultSize; i++) {
        returnArray[i] = result[i];
    }
    return returnArray;
}

int main() {
    char tickets[MAX_TICKETS][2][MAX_LEN];
    int ticketsSize = 0;
    
    scanf("%d", &ticketsSize);
    for (int i = 0; i < ticketsSize; i++) {
        scanf("%s %s", tickets[i][0], tickets[i][1]);
    }
    
    int returnSize;
    char** returnArray = solution(tickets, ticketsSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("\"%s\"", returnArray[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(V + E)²

DFS traversal with potential backtracking, where V is airports and E is tickets

✓ Linear Growth

Space Complexity

O(V + E)

Adjacency list storage plus recursion stack depth

✓ Linear Space

168.5K Views

Medium-High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler