How do you solve Destination City on LeetCode?

Destination City (LeetCode #1436) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The destination city is the only city that does not appear as a starting point in any path.

What is the brute force solution for Destination City?

The brute force approach for Destination City is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking each city to see if it has any outgoing paths. If a city has no outgoing paths, it is the destination city. This method is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Destination City?

Destination City uses the following concepts: Array, Hash Table, String. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Destination City?

Always clarify the problem statement and constraints before diving into coding. Think about edge cases, such as the minimum number of paths. Discuss your thought process and approach with the interviewer; they may guide you if you're stuck.

What are common mistakes when solving Destination City?

Not considering the case where a city has no outgoing paths. Confusing the direction of paths and misidentifying the destination.

#1436

Destination City

Easy

ArrayHash TableStringHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a set to track outgoing paths and directly identifies the destination city in a single pass. This is efficient and avoids redundant checks.

⚙️

Algorithm

3 steps

1Step 1: Create a set to store all cities with outgoing paths.
2Step 2: Populate the set with all starting cities from the paths.
3Step 3: Iterate through the paths again and check which city is not in the set. That city is the destination.

solution.py3 lines

1def destCity(paths):
2    outgoing = set(cityA for cityA, cityB in paths)
3    return next(cityB for cityA, cityB in paths if cityB not in outgoing)

ℹ

Complexity note: The time complexity is O(n) because we iterate through the paths twice, while the space complexity is O(n) due to the storage of outgoing paths.

1The destination city is the only city that does not appear as a starting point in any path.
2Using a set for efficient lookups allows us to reduce the time complexity significantly.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.