End of the Route

Easy

A traveler wrote down a trip as a set of legs legs but mixed up their order. Each leg is a pair [from, to]: the traveler went straight from the first city to the second. All legs join into a single chain with no repeats and no loops, so every city appears on the route once. Return the name of the city where the trip ended, the one with no leg leaving it.

Example 1

legs=[['Oslo', 'Bergen'], ['Tromso', 'Oslo'], ['Bergen', 'Stavanger']] → 'Stavanger'

The route is Tromso → Oslo → Bergen → Stavanger. Nothing leaves Stavanger, so that is the last stop.

Example 2

legs=[['Rome', 'Milan']] → 'Milan'

The only leg ends in Milan.

Example 3

legs=[['b', 'B'], ['a', 'b']] → 'B'

Case matters: "b" and "B" are different cities. The route is a → b → B.

Constraints

1 ≤ len(legs) ≤ 10⁵
legs[i].length == 2
A city name has 1 to 30 characters: English letters of either case and spaces
The legs form one chain with no loops, and no leg starts and ends in the same city

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table String

Similar problems

One-Row Typing Easy Dinner for Two Easy Phrases with Synonyms Easy Word from a License Plate Easy Distinct Morse Signals Easy

Input

legs=[['Oslo', 'Bergen'], ['Tromso', 'Oslo'], ['Bergen', 'Stavanger']]

Expected

'Stavanger'

Run checks the first 3 tests in your browser. Submit checks all 69 tests on the server, hidden ones included.