How do you solve the Destination City problem?

By scanning the list of paths and using a hash table to track cities with outgoing paths, you can quickly identify the city without an outgoing path as the destination.

What is the time complexity of the Destination City problem?

The time complexity is O(n), where n is the number of paths, because you scan through the list once and perform constant-time lookups.

What data structures are useful for the Destination City problem?

A set or hash table is ideal for tracking cities with outgoing paths, allowing for efficient identification of the destination city.

How does the pattern apply to other problems?

This problem demonstrates a common approach of scanning an array while using a hash table to quickly identify elements that meet specific conditions, applicable to a variety of array and graph traversal problems.

Can this problem have more than one destination city?

No, the problem guarantees there is exactly one destination city since the paths form a linear graph without loops.

#1436

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

旅行终点站

给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityA i , cityB i ] 表示该线路将会从 cityA i 直接前往 cityB i 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。题目数据保证线路图会形成一条不存…

数组哈希表字符串

题目描述

给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityA_i, cityB_i] 表示该线路将会从 cityA_i 直接前往 cityB_i 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。

题目数据保证线路图会形成一条不存在循环的线路，因此恰有一个旅行终点站。

示例 1：

输入：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
输出："Sao Paulo" 
解释：从 "London" 出发，最后抵达终点站 "Sao Paulo" 。本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo" 。

示例 2：

输入：paths = [["B","C"],["D","B"],["C","A"]]
输出："A"
解释：所有可能的线路是：
"D" -> "B" -> "C" -> "A". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
显然，旅行终点站是 "A" 。

示例 3：

输入：paths = [["A","Z"]]
输出："Z"

提示：

1 <= paths.length <= 100
paths[i].length == 2
1 <= cityA_i.length, cityB_i.length <= 10
cityA_i!= cityB_i
所有字符串均由大小写英文字母和空格字符组成。

lightbulb

解题思路

方法一：哈希表

根据题目描述，终点一定不会出现在所有 $\textit{cityA}$ 中，因此，我们可以先遍历一遍 $\textit{paths}$ ，将所有 $\textit{cityA}$ 放入一个集合 $\textit{s}$ 中，然后再遍历一遍 $\textit{paths}$ ，找到不在 $\textit{s}$ 中的 $\textit{cityB}$ 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为 $\textit{paths}$ 的长度。

1

2

3

4

5

class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        s = {a for a, _ in paths}
        return next(b for _, b in paths if b not in s)

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Candidate identifies the key insight: finding the city with no outgoing path.
question_mark
Candidate demonstrates an understanding of hash table or set usage for efficient lookups.
question_mark
Candidate efficiently handles edge cases like single-path graphs or varying city names.

warning

常见陷阱

外企场景

error
Mistaking the first city in the list as the destination without considering all paths.
error
Overcomplicating the solution by using unnecessary data structures.
error
Missing the linear time complexity requirement and attempting inefficient solutions like nested loops.

swap_horiz

进阶变体

外企场景

arrow_right_alt
The problem can be extended to find multiple destination cities in a more complex graph where multiple disconnected lines of paths exist.
arrow_right_alt
Consider adding a constraint that allows for more than one city to have no outgoing path, turning the problem into a search for all destination cities.
arrow_right_alt
Variant: What if the paths form a loop? How would the solution adapt to handle circular references?

help

常见问题

外企场景

继续练习

#1452 收藏清单 #1418 点菜展示表 #1487 保证文件名唯一