Easy

Quiz

#1436 Destination City

APPROACH

You are given an array paths where each entry paths[i] = [cityAi, cityBi] describes a one-way route from cityAi to cityBi. Find and return the terminal city — the one that has no outgoing route to any other city.

The routes are guaranteed to form a simple chain with exactly one terminal city.

Example 1:

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]

Output: "Sao Paulo"

Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

Example 2:

Input: paths = [["B","C"],["D","B"],["C","A"]]

Output: "A"

Explanation: All possible trips are:

"D" -> "B" -> "C" -> "A".

"B" -> "C" -> "A".

"C" -> "A".

"A".

Clearly the destination city is "A".

Example 3:

Input: paths = [["A","Z"]]

Output: "Z"

1 of 4

1:00

What is the optimal approach for this problem?