Trace the Complete Path of a Journey

You have a set of one-way tickets, each written as (from, to), in random order. Together they form one continuous route that visits no city twice. Return the cities in the order they're visited.

Example

Text

Input:  [("NewYork", "Chicago"), ("Boston", "Texas"),
         ("Missouri", "NewYork"), ("Texas", "Missouri")]
Output: Boston -> Texas -> Missouri -> NewYork -> Chicago

graph LR
    Boston --> Texas --> Missouri --> NewYork --> Chicago

Two observations solve the problem:

The starting city is the only from city that never appears as a to city: no ticket leads into it.
From any city, there's exactly one ticket leaving it, so the next city is determined.

Brute force: search the tickets for every step

Find the start by checking, for each ticket, whether any ticket arrives at its from city. Then repeatedly scan all tickets for the one that leaves the current city. A ticket is a String[] of length 2: {from, to}.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<String> trace(String[][] tickets) {
        List<String> path = new ArrayList<>();
        String start = null;
        for (String[] t : tickets) {
            boolean hasIncoming = false;
            for (String[] u : tickets) {
                if (u[1].equals(t[0])) hasIncoming = true;
            }
            if (!hasIncoming) {
                start = t[0];
                break;
            }
        }
        if (start == null) return path;
        String city = start;
        path.add(city);
        boolean moved = true;
        while (moved) {
            moved = false;
            for (String[] t : tickets) {
                if (t[0].equals(city)) {
                    city = t[1];
                    path.add(city);
                    moved = true;
                    break;
                }
            }
        }
        return path;
    }

    public static void main(String[] args) {
        String[][] tickets = {{"NewYork", "Chicago"}, {"Boston", "Texas"}, {"Missouri", "NewYork"}, {"Texas", "Missouri"}};
        System.out.println(String.join(" -> ", trace(tickets)));
    }
}

Output

Boston -> Texas -> Missouri -> NewYork -> Chicago

Time: O(n²): finding the start is O(n²), and each of the n steps scans all n tickets. Space: O(1) besides the output.

Optimal: a lookup table from each city to the next

Build two structures in one pass over the tickets:

next: Map<from, to>, so the next city is an O(1) lookup.
destinations: Set<to>, so "does any ticket arrive here?" is an O(1) check.

The start is the key of next that isn't in destinations. Then follow next until a city has no outgoing ticket.

Walkthrough:

Text

next         = { NewYork: Chicago, Boston: Texas, Missouri: NewYork, Texas: Missouri }
destinations = { Chicago, Texas, NewYork, Missouri }
start        = Boston   (the only key not in destinations)

city	next[city]
Boston	Texas
Texas	Missouri
Missouri	NewYork
NewYork	Chicago
Chicago	none → stop

Map.get returns null when the key is missing, and that null ends the loop.

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Main {
    static List<String> trace(String[][] tickets) {
        Map<String, String> next = new HashMap<>();
        Set<String> destinations = new HashSet<>();
        for (String[] t : tickets) {
            next.put(t[0], t[1]);
            destinations.add(t[1]);
        }
        String start = null;
        for (String from : next.keySet()) {
            if (!destinations.contains(from)) {
                start = from;
                break;
            }
        }
        List<String> path = new ArrayList<>();
        if (start == null) return path; // every city has an incoming ticket: the route is a loop
        for (String city = start; city != null; city = next.get(city)) {
            path.add(city);
        }
        return path;
    }

    public static void main(String[] args) {
        String[][] tickets = {{"NewYork", "Chicago"}, {"Boston", "Texas"}, {"Missouri", "NewYork"}, {"Texas", "Missouri"}};
        System.out.println(String.join(" -> ", trace(tickets)));
        System.out.println(trace(new String[][]{{"A", "B"}}));
        System.out.println(trace(new String[][]{}));
    }
}

Output

Boston -> Texas -> Missouri -> NewYork -> Chicago
[A, B]
[]

Time: O(n). Space: O(n).

Only one key of next is missing from destinations when the tickets form one route, so the iteration order of the HashMap does not change the result.

Edge cases

No tickets: the result is empty.
The tickets form a loop: no start exists, and the result is empty. Without the "visits no city twice" guarantee, following next from an arbitrary city could loop forever, so check the path length against n + 1 if the input can't be trusted.
Reusable tickets, several tickets from one city (LeetCode 332, Reconstruct Itinerary): this needs a graph search (Hierholzer's algorithm), not a simple lookup.