LeetCode 1436 - Destination City

In this problem, we are given a list of directed paths between cities. Each entry in paths has the form [cityA, cityB],

leetcodeeasyarrayhash-tablestring

LeetCode Problem 1436

Difficulty: 🟢 Easy
Topics: Array, Hash Table, String

Solution

Problem Understanding

In this problem, we are given a list of directed paths between cities. Each entry in paths has the form [cityA, cityB], which means there is a one way path from cityA to cityB.

The graph formed by these paths is guaranteed to represent a straight travel chain with no cycles. This guarantee is extremely important because it means:

  • There is exactly one city where the journey ends.
  • Every other city has at least one outgoing edge.
  • No city can lead back to a previously visited city.

The task is to find the destination city, which is the only city that never appears as a starting point in any path.

For example, if we have:

London -> New York
New York -> Lima
Lima -> Sao Paulo

then Sao Paulo is the destination city because no path starts from it.

The input size is very small, at most 100 paths, so efficiency is not a major concern. However, the problem is designed to test whether we can recognize the key graph property instead of overcomplicating the solution.

Some important observations from the constraints and guarantees:

  • Every path is directed.
  • There is exactly one valid answer.
  • No loops exist.
  • City names are strings, so hash based structures such as sets or maps are ideal.
  • Since the graph forms a line, we do not need graph traversal algorithms like DFS or BFS.

Important edge cases include:

  • A single path such as ["A", "Z"]
  • Cities appearing multiple times as intermediate stops
  • The destination city appearing only once in the entire input
  • Paths given in arbitrary order

Because the input order is not guaranteed to represent the travel order, we cannot simply return the last city from the final path.

Approaches

Brute Force Approach

A straightforward approach is to examine every destination city and check whether it ever appears as a starting city.

For every path [fromCity, toCity], we can scan the entire list again to determine whether toCity exists as any fromCity.

If we find a city that never appears as a source, that city must be the destination city.

This works correctly because the destination city is defined precisely as the city with zero outgoing paths.

However, this approach performs unnecessary repeated scans. For each city, we may traverse the entire list again, leading to quadratic time complexity.

Optimal Approach

The key insight is that the destination city is the only city that never appears as a starting city.

Instead of repeatedly scanning the input, we can store all source cities in a hash set. Then we iterate through the destination cities and return the one that is not present in the set.

Hash sets provide average O(1) lookup time, making the solution very efficient and simple.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Repeatedly scans all paths for each destination city
Optimal O(n) O(n) Uses a hash set for constant time lookups

Algorithm Walkthrough

  1. Create an empty hash set called starting_cities.

This set will store every city that appears as a source city in the paths. We use a hash set because membership checks are very fast. 2. Iterate through all paths.

For each path [from_city, to_city], insert from_city into the set. 3. Iterate through all paths again.

For each path [from_city, to_city], check whether to_city exists in starting_cities. 4. If to_city is not in the set, return it immediately.

Since the graph guarantees exactly one destination city, the first such city we encounter is the correct answer. 5. If no city is found, return an empty string.

In practice, this line is never reached because the problem guarantees a valid destination city.

Why it works

The destination city is defined as the city with no outgoing paths. Every city with outgoing paths appears as a source city somewhere in the input. Therefore, the only city missing from the set of source cities must be the destination city.

Because the problem guarantees exactly one such city, the algorithm always returns the correct answer.

Python Solution

from typing import List

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

        for from_city, to_city in paths:
            starting_cities.add(from_city)

        for from_city, to_city in paths:
            if to_city not in starting_cities:
                return to_city

        return ""

The implementation follows the algorithm directly.

First, we create a set named starting_cities. During the first loop, every source city is inserted into the set.

In the second loop, we examine each destination city. If a destination city is absent from the set, it means that city never appears as a starting point, so it must be the final destination.

The final return "" exists only for completeness. According to the problem constraints, a valid destination city always exists.

Go Solution

func destCity(paths [][]string) string {
    startingCities := make(map[string]bool)

    for _, path := range paths {
        fromCity := path[0]
        startingCities[fromCity] = true
    }

    for _, path := range paths {
        toCity := path[1]

        if !startingCities[toCity] {
            return toCity
        }
    }

    return ""
}

The Go solution uses a map[string]bool to simulate a hash set because Go does not have a built in set type.

The logic is identical to the Python version:

  • Store all starting cities in the map
  • Scan destination cities
  • Return the one not found in the map

No special handling for integer overflow is needed because the problem only involves strings and small input sizes.

Worked Examples

Example 1

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

First Pass, Build Starting Cities Set

Path Set After Insertion
["London", "New York"] {"London"}
["New York", "Lima"] {"London", "New York"}
["Lima", "Sao Paulo"] {"London", "New York", "Lima"}

Second Pass, Find Destination

Destination City In Starting Set? Action
"New York" Yes Continue
"Lima" Yes Continue
"Sao Paulo" No Return "Sao Paulo"

Final answer:

"Sao Paulo"

Example 2

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

First Pass

Path Set After Insertion
["B", "C"] {"B"}
["D", "B"] {"B", "D"}
["C", "A"] {"B", "D", "C"}

Second Pass

Destination City In Starting Set? Action
"C" Yes Continue
"B" Yes Continue
"A" No Return "A"

Final answer:

"A"

Example 3

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

First Pass

Path Set After Insertion
["A", "Z"] {"A"}

Second Pass

Destination City In Starting Set? Action
"Z" No Return "Z"

Final answer:

"Z"

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate through the paths list twice
Space O(n) The hash set stores up to all starting cities

The algorithm performs two linear passes over the input. Each hash set insertion and lookup operation takes average constant time, so the total runtime is linear.

The extra memory usage comes from storing the starting cities in the hash set. In the worst case, every path has a unique source city, so the set size grows to n.

Test Cases

from typing import List

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

        for from_city, to_city in paths:
            starting_cities.add(from_city)

        for from_city, to_city in paths:
            if to_city not in starting_cities:
                return to_city

        return ""

solution = Solution()

# Example 1
assert solution.destCity([
    ["London", "New York"],
    ["New York", "Lima"],
    ["Lima", "Sao Paulo"]
]) == "Sao Paulo"  # standard chain

# Example 2
assert solution.destCity([
    ["B", "C"],
    ["D", "B"],
    ["C", "A"]
]) == "A"  # unordered chain

# Example 3
assert solution.destCity([
    ["A", "Z"]
]) == "Z"  # single path

# Destination appears only once
assert solution.destCity([
    ["X", "Y"],
    ["Y", "Z"]
]) == "Z"  # simple ending node

# Paths given out of logical order
assert solution.destCity([
    ["C", "D"],
    ["A", "B"],
    ["B", "C"]
]) == "D"  # ordering should not matter

# City names with spaces
assert solution.destCity([
    ["New Delhi", "Dubai"],
    ["Dubai", "Paris"]
]) == "Paris"  # handles spaces correctly

# Longer chain
assert solution.destCity([
    ["A", "B"],
    ["B", "C"],
    ["C", "D"],
    ["D", "E"]
]) == "E"  # deeper chain

print("All tests passed!")

Test Summary

Test Why
Standard chain Verifies normal functionality
Unordered chain Ensures input order does not matter
Single path Tests minimum input size
Destination appears once Confirms destination detection
Out of order paths Prevents assumptions about ordering
City names with spaces Verifies string handling
Longer chain Tests multiple intermediate cities

Edge Cases

Single Path Input

The smallest valid input contains only one path, such as ["A", "Z"]. A naive implementation might overcomplicate traversal logic or assume multiple connections exist. Our implementation handles this naturally because the source set contains only "A", and "Z" is immediately identified as the only city without outgoing paths.

Paths Given in Random Order

The input paths are not guaranteed to appear in travel sequence order. For example:

["C", "D"]
["A", "B"]
["B", "C"]

A naive approach that assumes the last destination city in the list is the answer would fail. Our implementation avoids this issue entirely because it relies only on source city membership, not path ordering.

Intermediate Cities Appearing Multiple Times

Some cities may appear both as destinations and as sources. For example:

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

Here, "B" appears in both roles. A buggy implementation might incorrectly identify "B" as the destination after seeing it as a destination once. Our algorithm correctly checks whether the city also exists in the source set before returning it.