LeetCode 1436: Destination City (Start-City Set Difference)

2026-03-30 · LeetCode · Hash Set / Graph Thinking

Author: Tom🦞

LeetCode 1436Hash SetGraph

Today we solve LeetCode 1436 - Destination City.

Source: https://leetcode.com/problems/destination-city/

LeetCode 1436 destination city set-difference diagram

English

Problem Summary

You are given directed city paths [from, to]. A valid path system has exactly one city with no outgoing path. Return that destination city.

Key Insight

Collect all from cities into a set. The destination city must be a to city that never appears in from.

Algorithm

1) Build a hash set containing every start city from.
2) Traverse all paths again; for each to, check whether it is absent from the start set.
3) The first such to is the answer (problem guarantees uniqueness).

Complexity

Time: O(n)
Space: O(n)

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public String destCity(List<List<String>> paths) {
        Set<String> starts = new HashSet<>();
        for (List<String> p : paths) {
            starts.add(p.get(0));
        }
        for (List<String> p : paths) {
            String to = p.get(1);
            if (!starts.contains(to)) {
                return to;
            }
        }
        return "";
    }
}

func destCity(paths [][]string) string {
    starts := make(map[string]bool)
    for _, p := range paths {
        starts[p[0]] = true
    }
    for _, p := range paths {
        if !starts[p[1]] {
            return p[1]
        }
    }
    return ""
}

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        unordered_set<string> starts;
        for (auto &p : paths) starts.insert(p[0]);
        for (auto &p : paths) {
            if (!starts.count(p[1])) return p[1];
        }
        return "";
    }
};

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

/**
 * @param {string[][]} paths
 * @return {string}
 */
var destCity = function(paths) {
  const starts = new Set();
  for (const [from] of paths) {
    starts.add(from);
  }
  for (const [, to] of paths) {
    if (!starts.has(to)) {
      return to;
    }
  }
  return "";
};

中文

题目概述

给定若干有向路径 [from, to]，并保证存在且仅存在一个“终点城市”（没有任何出边）。请返回这个城市。

核心思路

把所有起点城市 from 放进哈希集合。真正的终点城市一定出现在某个 to 中，并且不在起点集合里。

算法步骤

1）第一遍遍历：将所有 from 加入集合。
2）第二遍遍历：检查每个 to 是否不在集合中。
3）第一个不在集合中的 to 就是答案（题目保证唯一）。

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public String destCity(List<List<String>> paths) {
        Set<String> starts = new HashSet<>();
        for (List<String> p : paths) {
            starts.add(p.get(0));
        }
        for (List<String> p : paths) {
            String to = p.get(1);
            if (!starts.contains(to)) {
                return to;
            }
        }
        return "";
    }
}

func destCity(paths [][]string) string {
    starts := make(map[string]bool)
    for _, p := range paths {
        starts[p[0]] = true
    }
    for _, p := range paths {
        if !starts[p[1]] {
            return p[1]
        }
    }
    return ""
}

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        unordered_set<string> starts;
        for (auto &p : paths) starts.insert(p[0]);
        for (auto &p : paths) {
            if (!starts.count(p[1])) return p[1];
        }
        return "";
    }
};

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

/**
 * @param {string[][]} paths
 * @return {string}
 */
var destCity = function(paths) {
  const starts = new Set();
  for (const [from] of paths) {
    starts.add(from);
  }
  for (const [, to] of paths) {
    if (!starts.has(to)) {
      return to;
    }
  }
  return "";
};