Given a list of directed paths, find the city that is never used as a starting point.
You are given a list of one-way travel routes between cities. Each route is represented by a pair of city names [from, to], meaning you can travel directly from from to to.
Exactly one city is the final destination: it never appears as a starting city in any route. Return that city name.
The routes form a valid chain-like travel plan, so there is a unique answer.
Input Format
paths: a list of pairs/lists, where each pair contains two city namesfromandto.- Each city name is a non-empty string.
- Every pair represents a directed edge from
fromtoto.
Output Format
- Return the name of the city that never appears in the
fromposition.
Constraints
- The destination city is unique.
1 <= paths.length- City names are case-sensitive strings.
- The input describes a valid set of routes with one terminal destination.
Example 1
Input
paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output
"Sao Paulo"
Explanation
London, New York, and Lima each appear as a starting city. Sao Paulo appears only as a destination, so it is the final city.
Example 2
Input
paths = [["B","C"],["D","B"],["C","A"]]
Output
"A"
Explanation
The starting cities are B, D, and C. The only city that never appears as a start is A.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.