Destination City - Practice Coding Problems

Destination City - Problem

You are given an 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.

Input & Output

Example 1 — Basic Chain

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

› Output: "Sao Paulo"

💡 Note: Following the path: London → New York → Lima → Sao Paulo. Sao Paulo has no outgoing path, so it's the destination.

Example 2 — Simple Path

$ Input: paths = [["B","C"],["D","B"],["C","A"]]

› Output: "A"

💡 Note: The path is D → B → C → A. City A appears as a destination but never as a source.

Example 3 — Single Path

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

› Output: "Z"

💡 Note: Only one path A → Z, so Z is the destination city with no outgoing paths.

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.

Visualization

Tap to expand

Understanding the Visualization

Input Paths

Array of city pairs representing directed paths

Find Pattern

Destination city has no outgoing path

Output

Return the city that only appears as destination

Key Takeaway

🎯 Key Insight: The destination city is the only city that appears as an arrival but never as a departure in any path

Asked in

G Google 15 a Amazon 12 Apple 8 f Facebook 6

The key insight is that the destination city appears as an arrival but never as a departure. Best approach uses a hash set to store all source cities, then finds the destination not in the set. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Hash Set Optimization	O(n)	O(n)	Use hash set to store all source cities, then find destination not in set
Brute Force	O(n²)	O(1)	For each city, check if it appears as a source in any path

Hash Set Optimization — Algorithm Steps

Create hash set of all source cities
Iterate through destinations
Return destination not found in source set

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Source Set

Add all source cities to hash set

Check Destinations

Look for destination not in source set

Found Answer

Return the destination city not found in sources

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_CITIES 1000
#define MAX_NAME_LEN 100

char* solution(char paths[][2][MAX_NAME_LEN], int pathCount) {
    // Simple array-based "hash set" for sources
    char sources[MAX_CITIES][MAX_NAME_LEN];
    int sourceCount = 0;
    
    // Collect all source cities
    for (int i = 0; i < pathCount; i++) {
        // Check if source already exists
        int exists = 0;
        for (int j = 0; j < sourceCount; j++) {
            if (strcmp(sources[j], paths[i][0]) == 0) {
                exists = 1;
                break;
            }
        }
        if (!exists) {
            strcpy(sources[sourceCount], paths[i][0]);
            sourceCount++;
        }
    }
    
    // Find destination that's not a source
    for (int i = 0; i < pathCount; i++) {
        char* destination = paths[i][1];
        int isSource = 0;
        
        for (int j = 0; j < sourceCount; j++) {
            if (strcmp(sources[j], destination) == 0) {
                isSource = 1;
                break;
            }
        }
        
        if (!isSource) {
            char* result = malloc(strlen(destination) + 1);
            strcpy(result, destination);
            return result;
        }
    }
    
    char* result = malloc(1);
    result[0] = '\0';
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simple parsing - assuming small input for demo
    char paths[100][2][MAX_NAME_LEN];
    int pathCount = 0;
    
    // Basic parsing logic here
    char* result = solution(paths, pathCount);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two separate O(n) passes through the paths array

✓ Linear Growth

Space Complexity

O(n)

Hash set stores up to n source cities

⚡ Linearithmic Space

31.5K Views

Medium Frequency

~10 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Set Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler