algoadvance

Leetcode 1436. Destination City

Problem Statement

You are given the paths array 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.

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". 
"A" is the only city with no outgoing paths.

Example 3:

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

Clarifying Questions

  1. Can we assume that there is exactly one destination city?
    • Yes, we can assume there is exactly one destination city.
  2. How large can the paths array be?
    • The paths array can have up to 100 paths.
  3. Are there any constraints on the names of the cities?
    • No specific constraints, names can be any string.

Strategy

  1. Use a set to store all the cities that have outgoing paths.
  2. Traverse through the paths array to add all cities that appear as the starting city of a path to the set.
  3. Traverse through the paths array again and for each destination city, check if it is not in the set of cities with outgoing paths. The first such city found is our destination city.

Code

Here is the C++ solution to the problem:

#include <vector>
#include <string>
#include <unordered_set>

using namespace std;

string destCity(vector<vector<string>>& paths) {
    unordered_set<string> outgoing;
    
    // Add all cities that have outgoing paths to the set
    for (const auto& path : paths) {
        outgoing.insert(path[0]);
    }
    
    // Find the city that does not have any outgoing path
    for (const auto& path : paths) {
        if (outgoing.find(path[1]) == outgoing.end()) {
            return path[1];
        }
    }
    
    // This return statement will never be reached because there is
    // always one destination city according to the problem statement
    return "";
}

Time Complexity

This approach ensures an efficient solution that runs in linear time and uses additional space proportional to the number of cities with outgoing paths.

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