Leetcode – Destination City Solution

Spread the love

One of the problems that make you think in terms of data manipulation and graph traversal is the “Destination City” problem. This problem falls under the categories of strings and hash tables, and solving it efficiently requires keen observational skills.

In this comprehensive guide, we’ll explore:

  1. Problem Statement
  2. A Basic Solution
  3. Hash Table-based Optimized Solution
  4. Python Code Implementations
  5. Edge Cases and Testing
  6. Time and Space Complexity Analysis
  7. Conclusion

1. Problem Statement

You are given the array paths, where paths[i] = [cityA_i, cityB_i] means there exists a direct path going from cityA_i to cityB_i. 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"

Example 2:

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

2. A Basic Solution

The naive way to solve this problem is to:

  1. Create two sets or lists, one for starting cities and the other for destination cities.
  2. Loop through each pair and fill these sets.
  3. Return the city that appears only in the destination set and not in the starting set.

3. Hash Table-based Optimized Solution

The problem can be solved more elegantly by utilizing hash tables to keep track of the cities that have outgoing paths. By the end of the traversal, the city that doesn’t have an outgoing path will be our answer.

4. Python Code Implementations

Basic Implementation

def destCity(paths):
    start_cities = set()
    end_cities = set()
    
    for path in paths:
        start_cities.add(path[0])
        end_cities.add(path[1])
        
    for city in end_cities:
        if city not in start_cities:
            return city

Hash Table-based Optimized Implementation

def destCity(paths):
    outgoing = {}
    
    for start, end in paths:
        outgoing[start] = end
        
    for end in outgoing.values():
        if end not in outgoing:
            return end

5. Edge Cases and Testing

You can validate your function by testing it with a variety of test cases:

# Test 1
assert destCity([["London", "New York"], ["New York", "Lima"], ["Lima", "Sao Paulo"]]) == "Sao Paulo"
# Test 2
assert destCity([["B", "C"], ["D", "B"], ["C", "A"]]) == "A"
# Test 3 (Edge case)
assert destCity([["A", "Z"]]) == "Z"

6. Time and Space Complexity Analysis

Time Complexity

Both approaches have a time complexity of O(n), where n is the number of city pairs, as we’re traversing the list of paths once.

Space Complexity

The space complexity for the basic solution is O(n) due to the use of sets, and it’s O(1) for the optimized solution since we are using the existing data structure.

7. Conclusion

The “Destination City” problem is a fantastic exercise for understanding data manipulation and hash table usage in Python. It tests your ability to map relationships and extract information from those mappings efficiently.

This article provided you with a fundamental approach to the problem and also taught you how to optimize it further using hash tables. We looked at Python implementations for both methods and even discussed testing and complexity analysis.

Leave a Reply