Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Destination City solution and explanation

EasyArrayHash TableString5 min read79.5% acceptanceUpdated 9 Apr 2026
Asked atYelpYandexAmazonMeta
Practise Destination City
5:27
Destination City - Leetcode 1436 - PythonNeetCodeIO · 5:27 · 8K viewsWatch on YouTube
9 more videos on this problem
  1. Destination City - Leetcode 1436 - PythonNeetCodeIO · 5:27 · 8K views
  2. Destination City | 2 Approaches | Leetcode-1436codestorywithMIK · 8:58 · 6K views
  3. 1436.Destination City | Leetcode | EasyChhavi Bansal · 6:03 · 3K views
  4. 1436. Destination City (Leetcode Easy)Programming Live with Larry · 2:28 · 1K views
  5. LeetCode 1436 Destination City - Solutiion Using SetAlgorithmicIQ · 3:43 · 882 views
  6. Leetcode 1436. Destination City Python SolutionsTechZoo · 4:00 · 678 views
  7. Leetcode | 1436. Destination City | Easy | Java SolutionDeveloper Docs · 6:23 · 668 views
  8. LeetCode 1436. Destination City Solution Explained - JavaAlgorithms and Data Structures Course · 7:23 · 663 views
  9. Destination City (Leetcode 1436)Coding Interviews · 10:56 · 601 views
  10. Destination City | Leetcode #1436 | EasyMorning Byte · 2:23 · 332 views

The problem

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.

def destCity(paths):
    starting_cities = set()
    for path in paths:
        starting_cities.add(path[0])
    for path in paths:
        if path[1] not in starting_cities:
            return path[1]
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public String destCity(List<List<String>> paths) {
        Set<String> startingCities = new HashSet<>();
        for (List<String> path : paths) {
            startingCities.add(path.get(0));
        }
        for (List<String> path : paths) {
            if (!startingCities.contains(path.get(1))) {
                return path.get(1);
            }
        }
        return "";
    }
}
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

string destCity(vector<vector<string>>& paths) {
    unordered_set<string> starts;
    for (auto& path : paths) {
        starts.insert(path[0]);
    }
    for (auto& path : paths) {
        if (starts.find(path[1]) == starts.end()) {
            return path[1];
        }
    }
    return "";
}
function destCity(paths) {
    const startingCities = new Set();
    for (let path of paths) {
        startingCities.add(path[0]);
    }
    for (let path of paths) {
        if (!startingCities.has(path[1])) {
            return path[1];
        }
    }
    return '';
}
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

char* destCity(char*** paths, int pathsSize, int* pathsColSize) {
    bool outgoing[100] = {false};
    char* cities[200];
    int cityCount = 0;
    
    for (int i = 0; i < pathsSize; i++) {
        int startIndex = -1, endIndex = -1;
        for (int j = 0; j < cityCount; j++) {
            if (strcmp(cities[j], paths[i][0]) == 0) startIndex = j;
            if (strcmp(cities[j], paths[i][1]) == 0) endIndex = j;
        }
        if (startIndex == -1) cities[cityCount++] = paths[i][0];
        if (endIndex == -1) cities[cityCount++] = paths[i][1];
        
        outgoing[startIndex] = true;
    }
    
    for(int i = 0; i < pathsSize; i++) {
        char* destination = paths[i][1];
        int j;
        for (j = 0; j < cityCount; j++) {
            if (strcmp(cities[j], destination) == 0 && !outgoing[j]) {
                return destination;
            }
        }
    }
    return "";
}
using System;
using System.Collections.Generic;

public class Solution {
    public string DestCity(IList<IList<string>> paths) {
        HashSet<string> startingCities = new HashSet<string>();
        foreach (var path in paths) {
            startingCities.Add(path[0]);
        }
        foreach (var path in paths) {
            if (!startingCities.Contains(path[1])) {
                return path[1];
            }
        }
        return "";
    }
}

This Python solution uses a set to track each of the starting cities. For each path, it checks if the destination is not in the set of starting cities. The first such city found is the destination city.

Complexity

Time Complexity: O(n), due to hashing operations in the set.
Space Complexity: O(n), due to storage of starting 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.

def destCity(paths):
    city_count = {}
    for path in paths:
        city_count[path[0]] = city_count.get(path[0], 0) + 1
        city_count.setdefault(path[1], 0)
    for path in paths:
        if city_count[path[1]] == 0:
            return path[1]
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public String destCity(List<List<String>> paths) {
        Map<String, Integer> cityCount = new HashMap<>();
        for (List<String> path : paths) {
            cityCount.put(path.get(0), cityCount.getOrDefault(path.get(0), 0) + 1);
            cityCount.putIfAbsent(path.get(1), 0);
        }
        for (List<String> path : paths) {
            if (cityCount.get(path.get(1)) == 0) {
                return path.get(1);
            }
        }
        return "";
    }
}
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

string destCity(vector<vector<string>>& paths) {
    unordered_map<string, int> cityCount;
    for (auto& path : paths) {
        cityCount[path[0]]++;
        if (cityCount.find(path[1]) == cityCount.end()) {
            cityCount[path[1]] = 0;
        }
    }
    for (auto& path : paths) {
        if (cityCount[path[1]] == 0) {
            return path[1];
        }
    }
    return "";
}
function destCity(paths) {
    const cityCount = {};
    paths.forEach(path => {
        cityCount[path[0]] = (cityCount[path[0]] || 0) + 1;
        if (!cityCount.hasOwnProperty(path[1])) {
            cityCount[path[1]] = 0;
        }
    });
    for (let path of paths) {
        if (cityCount[path[1]] === 0) {
            return path[1];
        }
    }
    return '';
}
#include <stdio.h>
#include <string.h>

char* destCity(char paths[][2][100], int pathsSize) {
    char start[100][100];
    char end[100][100];
    int startCount = 0, endCount = 0;
    
    for (int i = 0; i < pathsSize; i++) {
        strcpy(start[startCount++], paths[i][0]);
        strcpy(end[endCount++], paths[i][1]);
    }
    
    for (int i = 0; i < endCount; i++) {
        int j;
        for (j = 0; j < startCount; j++) {
            if (strcmp(end[i], start[j]) == 0)
                break;
        }
        if (j == startCount) {
            return end[i];
        }
    }
    return "";
}
using System;
using System.Collections.Generic;

public class Solution {
    public string DestCity(IList<IList<string>> paths) {
        Dictionary<string, int> cityCount = new Dictionary<string, int>();
        foreach (var path in paths) {
            if (!cityCount.ContainsKey(path[0]))
                cityCount[path[0]] = 0;
            cityCount[path[0]]++;
            if (!cityCount.ContainsKey(path[1]))
                cityCount[path[1]] = 0;
        }
        foreach (var path in paths) {
            if (cityCount[path[1]] == 0) {
                return path[1];
            }
        }
        return "";
    }
}

The Python solution keeps a count of appearances of cities as starting points. We then determine the destination city by finding one that has no outgoing paths (count == 0).

Complexity

Time Complexity: O(n) due to dictionary operations.
Space Complexity: O(n) for maintaining the city count dictionary.

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.

function destCity(paths: string[][]): string {
    const s = new Set<string>(paths.map(([a, _]) => a));
    return paths.find(([_, b]) => !s.has(b))![1];
}
func destCity(paths [][]string) string {
	s := map[string]bool{}
	for _, p := range paths {
		s[p[0]] = true
	}
	for _, p := range paths {
		if !s[p[1]] {
			return p[1]
		}
	}
	return ""
}
use std::collections::HashSet;

impl Solution {
    pub fn dest_city(paths: Vec<Vec<String>>) -> String {
        let s = paths
            .iter()
            .map(|p| p[0].clone())
            .collect::<HashSet<String>>();
        paths.into_iter().find(|p| !s.contains(&p[1])).unwrap()[1].clone()
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Using a Set to Track Cities with Outgoing Paths

Time Complexity: O(n), due to hashing operations in the set.
Space Complexity: O(n), due to storage of starting cities.

Track and Count Incoming Cities

Time Complexity: O(n) due to dictionary operations.
Space Complexity: O(n) for maintaining the city count dictionary.

Hash Table–

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.

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.

Comments

Now write it yourselfClose this page and solve Destination City in the editor, without looking.
Practise Destination City