87. Final Stop
A parcel courier follows a single trip that visits several cities one after another without ever returning to a city already visited. The trip is described by the array routes, where each entry routes[i] = [from, to] means the courier drives directly from city from to city to. The legs together form one unbroken chain, but they may be listed in any order.
Return the name of the final city of the trip, meaning the city where a leg ends and from which no other leg departs. City names are case-sensitive.
Example 1
- Input:
- routes = [["pune","goa"],["goa","kochi"],["delhi","pune"]]
- Output:
- "kochi"
- Explanation:
The legs chain as delhi -> pune -> goa -> kochi, and kochi has no outgoing leg.
Example 2
- Input:
- routes = [["x","y"]]
- Output:
- "y"
- Explanation:
With a single leg x -> y, the courier finishes in y.
Constraints
1 ≤ routes.length ≤ 103
routes[i].length == 2
1 ≤ from.length, to.length ≤ 20; names consist of English letters and digits
The legs form exactly one chain with no repeated city.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(n)