## Find a Canonical Shortest Round Trip Through Flights ### Problem Implement `shortestRoundTrip(flights, start) -> route`. Each element of `flights` is a directed flight `[from, to]`. Return a route that starts at `start`, follows one or more listed flights, and returns to `start` using the minimum possible number of flights. Include `start` at both ends of the returned array. If several shortest round trips exist, return the lexicographically smallest full airport sequence. Airport codes compare by ordinary ASCII order at the first differing character; if one code is a prefix of another, the shorter code comes first. Return an empty array if no round trip exists. ### Portable Contract - `flights` is a JSON array of two-string arrays `[from, to]`. - `0 <= flights.length <= 8,000`. - Each airport code contains `1` through `8` uppercase ASCII letters `A` through `Z`. - There are at most `4,000` distinct airport codes across `flights` and `start`. - Flights are directed. Duplicate flight pairs are allowed but do not create a different airport sequence. - A self-loop `[start, start]` is a valid one-flight round trip and returns `[start, start]`. - Do not modify `flights`. - Let `B` be the compact UTF-8 JSON byte length of `[flights,start]`: no whitespace outside strings, with every quote, comma, and bracket counted. Inputs satisfy `B <= 160,000`. - Let `R` be the compact UTF-8 JSON byte length of the returned string array under the same rule. Inputs guarantee `R <= 64,000`, so the serialized input plus result is at most `224,000` bytes. - Target `O((V + E) log E)` time or better and `O(V + E)` auxiliary space for distinct airports `V` and listed flights `E`. All four languages use only strings and homogeneous nested string arrays: `list[list[str]]` and `list[str]` in Python, arrays in JavaScript, `List<List<String>>` and `List<String>` in Java, and `vector<vector<string>>` and `vector<string>` in C++. ```hint Separate reachability from tie-breaking First determine how many flights are needed to get back to the start; then use that information to compare only choices that can still complete a shortest route. ``` ```hint Direct every search correctly Distances to the start are easier to compute when incoming and outgoing adjacency are not confused. ``` ### Examples ```text flights = [["SFO", "LAX"], ["LAX", "SEA"], ["SEA", "SFO"], ["LAX", "SFO"]] start = "SFO" route = ["SFO", "LAX", "SFO"] ``` ```text flights = [["A", "C"], ["C", "A"], ["A", "B"], ["B", "A"]] start = "A" route = ["A", "B", "A"] ``` ```text flights = [["A", "B"], ["B", "C"]] start = "A" route = [] ``` ### Discussion Requirements - Explain why a depth-first search can find some round trip but does not by itself guarantee the shortest one. - State how the algorithm guarantees one canonical answer among equal-length routes. - Cover duplicate flights, a self-loop, an airport that cannot return, and multiple shortest cycles. - Account for the cost of sorting or otherwise ordering adjacency lists.