Skip to main content
Talentd

Destination City - Solution & Explanation

EasyArrayHash TableString14 min readAsked at: Amazon, Meta, Yandex +1
Practice this problem

Problem Statement

You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBi. Return the destination city, that is, the city without any path outgoing to another city.

It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.

 

Example 1:

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo" 
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

Example 2:

Input: paths = [["B","C"],["D","B"],["C","A"]]
Output: "A"
Explanation: All possible trips are: 
"D" -> "B" -> "C" -> "A". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
Clearly the destination city is "A".

Example 3:

Input: paths = [["A","Z"]]
Output: "Z"

 

Constraints:

  • 1 <= paths.length <= 100
  • paths[i].length == 2
  • 1 <= cityAi.length, cityBi.length <= 10
  • cityAi != cityBi
  • All strings consist of lowercase and uppercase English letters and the space character.

Approach Overview

Problem Overview: You are given a list of travel paths where paths[i] = [cityA, cityB] means there is a direct trip from cityA to cityB. The paths form a line without cycles. Your task is to find the final destination city — the one that never appears as a starting city.

Approach 1: Using a Set to Track Cities with Outgoing Paths (O(n) time, O(n) space)

The key observation: the destination city never appears as a starting city in any path. Iterate through the list and insert every cityA into a hash set. This set represents all cities that have outgoing paths. Then iterate through the paths again and check each cityB. The first city not present in the set must be the final destination. Hash lookups run in constant time, so the entire process takes linear time relative to the number of paths. This method uses a hash table or set for efficient membership checks and works well for general cases.

Approach 2: Track and Count Incoming Cities (O(n) time, O(n) space)

Another way to think about the problem is through incoming edges. Every intermediate city appears both as a destination and as a starting city. The final city appears only as a destination. Use a hash map to count incoming occurrences for each city while also tracking cities that start paths. Iterate through all pairs in the array of paths and increment the count for cityB. After processing all paths, scan the map and return the city that has incoming paths but never appears as a start city. This approach models the travel routes like a simple directed graph and uses efficient lookups from a hash table.

Recommended for interviews: The set-based approach is usually what interviewers expect. It shows you quickly identified the key property: the destination city has zero outgoing edges. The implementation is concise and runs in O(n) time with O(n) space. Mentioning the graph interpretation (incoming vs outgoing edges) demonstrates deeper understanding of how the problem relates to common patterns in string and path traversal problems.

Approach 1: Using a Set to Track Cities with Outgoing Paths

The idea is to determine which city does not have any outgoing paths. This can be done by keeping track of all cities that appear as the starting city of a path. The destination city is the one that is not in this set but appears as an ending city in the path list.

This C solution uses an array to simulate a set to track which cities have outgoing paths. We iterate over the paths, storing cities in an array and marking those that appear as starting cities. Finally, we check which city does not appear as a starting city and return it as the destination.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) due to linear checks within loops.
Space Complexity: O(n), where n is the number of cities.

Try this approach in the editor →

Approach 2: Track and Count Incoming Cities

This approach involves counting occurrences of each city as an endpoint. The destination city will be the one whose occurrence as a destination is not matched by an occurrence as a start.

This C solution involves copying the destination cities into an array and checking each destination city against the start cities. The city not found among the start cities is returned as the destination city.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), since it includes iterating through paths multiple times.
Space Complexity: O(n) for storing city names.

Try this approach in the editor →

Approach 3: Hash Table

According to the problem description, the destination city will not appear in any of the cityA. Therefore, we can first traverse the paths and put all cityA into a set s. Then, we traverse the paths again to find the cityB that is not in s.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of paths.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using a Set to Track Cities with Outgoing Paths

Time Complexity: O(n^2) due to linear checks within loops.
Space Complexity: O(n), where n is the number of cities.

Track and Count Incoming Cities

Time Complexity: O(n^2), since it includes iterating through paths multiple times.
Space Complexity: O(n) for storing city names.

Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Set of Cities with Outgoing PathsO(n)O(n)Best general solution. Simple logic with fast hash lookups.
Track Incoming Cities with MapO(n)O(n)Useful when modeling the paths as directed graph edges.

Video Solution

Destination City - Leetcode 1436 - Python • NeetCodeIO • 8,071 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Destination City easy or hard?
Destination City is classified as an Easy problem. The challenge mainly involves recognizing that the final city has no outgoing edges and implementing a simple hash-based lookup to identify it.
How to solve Destination City in O(n)?
Iterate through all paths and insert every starting city into a hash set. Then iterate again and check each destination city. The city not present in the set is the final destination. Hash lookups make this check constant time, keeping the total complexity O(n).
What is the best approach for Destination City?
The hash set approach is the most efficient and commonly used solution. Store every starting city in a set, then check each destination city to find the one that never appears as a start. This runs in O(n) time with O(n) space and requires only two passes through the paths list.
Is Destination City asked at Google/Amazon/Meta?
Destination City represents a simplified graph and hash table problem pattern commonly used in interviews. Variations of this idea appear in coding interviews at companies like Amazon and Google where candidates must detect nodes with no outgoing edges.
What data structure is used in Destination City?
The typical solution uses a hash set or hash map. A set stores cities with outgoing paths for constant-time membership checks. This allows you to quickly identify the city that only appears as a destination.
What is the time complexity of Destination City?
The optimal solution runs in O(n) time where n is the number of paths. Each path is processed a constant number of times, and hash set lookups are O(1) on average. Space complexity is O(n) to store the cities with outgoing paths.
Destination City Python or Java solution approach?
Both Python and Java implementations follow the same idea: store all starting cities in a set, then scan for a destination city not present in that set. Python typically uses a built-in set, while Java uses HashSet for constant-time lookups.

Ready to solve this problem?

Practice Destination City with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays