algoadvance

Leetcode 1436. Destination City

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. Where cityA_i is the starting point and cityB_i is the destination.

Return the destination city, that is, the city without any path outgoing from it.

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

Example:

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 has no outgoing path.

Clarifying Questions:

1. Can paths contain duplicate city names (i.e., different routes starting from or leading to the same city)?
   • Each city name is unique in terms of its role on the graph.
2. What is the maximum length of paths?
   • The maximum length of paths can typically be assumed to be 100.

Strategy

1. Given that the paths form a straight line and there’s only one destination city, we need to identify the city that does not appear as a starting city in any of the given paths.
2. We can utilize a set to track all the starting cities.
3. Iterate through the given paths to populate this set.
4. Once we have the set of all starting cities, the destination city will be the one that is not in this starting set but appears as an ending city in one of the paths.

Code

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {
    public String destCity(List<List<String>> paths) {
        Set<String> startingCities = new HashSet<>();
        
        // Add all starting cities to the set
        for (List<String> path : paths) {
            startingCities.add(path.get(0));
        }
        
        // Check each ending city to see if it's not in the set of starting cities
        for (List<String> path : paths) {
            String endCity = path.get(1);
            if (!startingCities.contains(endCity)) {
                return endCity;
            }
        }
        
        // The problem guarantees there will always be a destination city,
        // so it's safe to return null or a default value here.
        return null;
    }
}

Time Complexity

• Time Complexity: O(n), where n is the number of paths. This is because we iterate through the paths list twice: once to populate the set of starting cities, and once to determine the destination city.
• Space Complexity: O(n), for storing the set of starting cities. In the worst case, the number of unique starting cities can be equal to the number of paths.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?