💬 Discord
Sign In
NeetCode #72LC-1436EasyArrays & Hashing
← Back to All Problems

#72 · #1436 · Destination City(旅行终点站)

📌 Problem Statement & Constraints

You are given an array paths where paths[i] = [cityA, cityB] means there is a direct path from cityA to cityB. Return the destination city, the one with no outgoing path, guaranteed to exist. Constraints: 1 <= paths.length <= 100; all city names are distinct strings.

💡 Core Algorithmic Approaches

  1. The destination is the city that appears only as a second element across all pairs.
  2. Collect all source cities into a set, then find a city that appears as a destination but not in that set.
  3. Because the destination is guaranteed to exist and the graph is a straight chain, exactly one such city exists.
  4. An alternative is to start from any source and follow the chain until no outgoing edge remains.

💻 Benchmark Python3 Implementation

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

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass to build the source set and one pass to search for the destination.
💾 Space Complexity
O(n) for the source set.

⚠️ Interview Pitfalls & Follow-ups

  • Collecting destinations instead: a city with no incoming path is the origin, not the destination.
  • Counting occurrences of each city: counting is not enough -- a city could appear twice as a source and once as a destination. The set-based check is precise.
  • Assuming the first pair's second element is the destination: the paths are unordered, so the chain may not start at paths[0].