Leetcode 1436: Destination City

Input: The input consists of an array `paths`, where each element is a pair of strings `[cityAi, cityBi]` representing a direct path from `cityAi` to `cityBi`.

Example: paths = [['Paris', 'Berlin'], ['Berlin', 'Madrid'], ['Madrid', 'Lisbon']]

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.

Output: The output is the name of the destination city, which is the city that does not have any outgoing path.

Example: 'Lisbon'

Constraints:

• The output is a string representing the destination city.

Goal: To find the city that has no outgoing paths by iterating through the `paths` array.

Steps:

• Step 1: Create a set to store cities with outgoing paths.

• Step 2: For each pair in the `paths` array, mark `cityAi` as having an outgoing path.

• Step 3: The city that is not in the set of cities with outgoing paths is the destination city.

Goal: Ensure that the solution efficiently handles paths with up to 100 pairs.

Steps:

• The solution should handle up to 100 paths.

• Strings have a length of up to 10 characters.

Assumptions:

• The input paths array contains valid pairs of strings.

• The graph of cities forms a line with no loops.

• Input: paths = [['Paris', 'Berlin'], ['Berlin', 'Madrid'], ['Madrid', 'Lisbon']]

• Explanation: Starting from 'Paris', we reach 'Lisbon' by traveling through 'Berlin' and 'Madrid'. 'Lisbon' is the destination city as it has no outgoing path.

• Input: paths = [['A', 'B'], ['B', 'C'], ['C', 'D']]

• Explanation: Following the path 'A' -> 'B' -> 'C' -> 'D', we find that 'D' is the destination city as there is no path from it to another city.

Approach: To find the destination city, we can iterate over the list of paths and track cities that have outgoing paths. The destination city is the one that is not present in the list of cities with outgoing paths.

Observations:

• The graph forms a line, so there is exactly one destination city.

• We can use a set to efficiently track cities with outgoing paths and then identify the city without an outgoing path.

Steps:

• Step 1: Initialize a set to store cities that have outgoing paths.

• Step 2: Iterate through each path and add `cityAi` to the set.

• Step 3: The city that is not in the set is the destination city, and return it.

Empty Inputs:

• The input will always contain at least one path, so there will be no empty input.

Large Inputs:

• The algorithm should handle paths up to the maximum limit efficiently.

Special Values:

• All cities are distinct, and there are no cycles in the graph.

Constraints:

• Ensure that the solution is efficient for input sizes up to the limit.

string destCity(vector<vector<string>>& paths) {
    map<string, string> mp;
    for(auto s: paths)
        mp[s[0]] = s[1];
    
    string ans = paths[0][0];
    while(mp.count(ans)) {
        ans = mp[ans];
    }
    return ans;
}

1 : Function Definition

string destCity(vector<vector<string>>& paths) {

Defines the function `destCity`, which takes a reference to a 2D vector of strings `paths` representing direct routes between cities.

2 : Variable Initialization

    map<string, string> mp;

Initializes a map `mp` to store the start and destination city pairs. The key is the starting city, and the value is the destination city.

3 : Loop

    for(auto s: paths)

Iterates through each pair of cities in the `paths` vector.

4 : Map Insertion

        mp[s[0]] = s[1];

Inserts each pair of cities from the `paths` vector into the map `mp`. The start city `s[0]` maps to the destination city `s[1]`.

5 : Variable Initialization

    string ans = paths[0][0];

Initializes the variable `ans` with the first city in the `paths` vector, assuming it is the starting city.

6 : Loop

    while(mp.count(ans)) {

Starts a while loop that continues as long as the current city `ans` is a key in the map `mp`, meaning there's a next city in the path.

7 : Map Lookup

        ans = mp[ans];

Updates `ans` to the destination city by looking up the current city in the map `mp`.

8 : Return Statement

    return ans;

Returns the value of `ans`, which is the final destination city after traversing all the paths.

Best Case: O(n) where n is the number of paths.

Average Case: O(n) for iterating through all paths and set operations.

Worst Case: O(n) where n is the number of paths.

Description: The time complexity is O(n) where n is the number of paths.

Best Case: O(n) if all cities are unique.

Worst Case: O(n) where n is the number of cities (since we may store all cities with outgoing paths).

Description: The space complexity is O(n) due to the storage of cities with outgoing paths in a set.

Leetcode 1436: Destination City

Explore →