#1436

Destination City

newbie · 180 · lc easy +15 · verified · 79.5% accepted · 2,311 likes · top 91%

Description

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"

Code

1

2

3

class Solution:
    def destCity(self, paths: List[List[str]]) -> str:

class Solution:
    def destCity(self, paths: List[List[str]]) -> str: