Destination City

Easy

Yelp

1 view

Topics:

ArraysStringsGraphs

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" 
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". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
Clearly the destination city is "A".

Example 3:

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

Constraints:

1 <= paths.length <= 100
paths[i].length == 2
1 <= cityA_i.length, cityB_i.length <= 10
cityA_i != cityB_i
All strings consist of lowercase and uppercase English letters and the space character.

Try coding it in LeetCode

Destination City

Easy

Yelp

1 view

Topics:

ArraysStringsGraphs

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" 
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". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
Clearly the destination city is "A".

Example 3:

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

Constraints:

1 <= paths.length <= 100
paths[i].length == 2
1 <= cityA_i.length, cityB_i.length <= 10
cityA_i != cityB_i
All strings consist of lowercase and uppercase English letters and the space character.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can I assume that there will always be exactly one destination city, meaning there's always a city with an incoming but no outgoing path?
What are the constraints on the length of the city names (strings)?
Can a city appear as both a starting and destination city in multiple paths?
Can the input list of paths ever be empty or null?
If there's an invalid input (e.g., no destination city), what should I return? Should I throw an exception or return a specific value like null or an empty string?

Brute Force Solution

Approach

The brute force approach to finding the destination city involves checking every possible city to see if it's the final one. We'll start with the first city in each route and eliminate cities that are departure points.

Here's how the algorithm would work step-by-step:

Look at each travel route individually.
Identify all cities that are starting points in at least one route.
Also, identify all cities that are ending points in at least one route.
Now, compare the lists. See if there is any ending point that is never a starting point.
If you find a city that's only an ending point and never a starting point, that's your destination city.

Code Implementation

def find_destination_city(routes):
    starting_cities = set()
    ending_cities = set()

    for route in routes:
        starting_city = route[0]
        destination_city = route[1]

        starting_cities.add(starting_city)
        ending_cities.add(destination_city)

    # The set of possible destinations has been identified.

    for possible_destination in ending_cities:
        # Check if city is ONLY in the ending cities list.

        if possible_destination not in starting_cities:
            # If the ending city is never a starting city, done!

            return possible_destination
    return None

Big(O) Analysis

Time Complexity

O(n) – Let n be the number of routes (the length of the `paths` input). Step 2 iterates through all routes to identify starting cities, taking O(n) time. Step 3 iterates through all routes to identify ending cities, taking O(n) time. Step 4 iterates through the list of ending cities and, for each ending city, checks against the list of starting cities, also taking O(n) time in the worst case since it would at most iterate n times for all the routes. The overall time complexity is therefore O(n) + O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The algorithm identifies starting and ending cities, storing them in lists. In the worst-case scenario, where each route involves distinct cities, the lists of starting and ending cities can grow up to a size proportional to the number of routes, N. Comparing these lists also requires iterating over these lists that are of size N. Therefore, the auxiliary space used is linearly proportional to the number of routes, N, resulting in O(N) space complexity.

Optimal Solution

Approach

The problem gives a list of routes, where each route goes from one city to another. The goal is to find the city that is the final destination, meaning it's reached but never departed from. The key idea is to identify cities that are only ever arrived at, and never listed as a starting point.

Here's how the algorithm would work step-by-step:

Make a list of all the cities that appear as starting points for any of the routes.
Look at each route and identify the destination city.
Check if each destination city is also present in the list of starting cities.
The destination city that is not found in the starting cities list is the final destination; that's your answer.

Code Implementation

def find_destination_city(routes):
    starting_cities = set()
    # Collect all departure cities
    for route in routes:
        starting_cities.add(route[0])

    for route in routes:
        destination_city = route[1]
        # Check if destination is also a start
        if destination_city not in starting_cities:

            # If not, it's the final destination
            return destination_city

    return None # Should not normally reach here

Big(O) Analysis

Time Complexity

O(n) – Let n be the number of routes in the input list. Creating the set of starting cities involves iterating through the routes once, taking O(n) time. Identifying the destination city requires another iteration of the routes, also O(n). Finally, checking if each destination city is present in the set of starting cities takes O(1) on average for set lookups but can take up to O(n) in a worst case scenario. Therefore the algorithm is O(n) in average cases and O(n^2) worst case.

Space Complexity

O(N) – The algorithm creates a set to store the starting cities. In the worst-case scenario, all starting cities are unique, leading to a set of size N, where N is the number of routes. Therefore, the auxiliary space required is proportional to the number of routes in the input. This results in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input list of paths	Return an empty string or null, indicating no destination city is found, or throw an exception based on problem requirements.
Input list containing only one path	The destination city is simply the second city in the single path.
All paths form a single linear route (A -> B -> C -> D)	The last city in the chain is the destination city; solution should traverse the paths to identify it.
Paths contain cycles (A -> B -> C -> A)	Cycles should not affect the determination of the destination city, as the destination will not have an outgoing path even within a cycle.
Multiple possible destination cities (invalid input according to problem statement, but handle gracefully)	Return one of the destination cities, throw an error, or return an empty string as the problem states a single destination should exist.
City names contain special characters or are very long strings	String operations should handle special characters and long strings efficiently without causing errors (check for memory limits with extremely large strings).
Large input list of paths (performance considerations)	Using a hash set or dictionary for efficient lookups ensures the algorithm scales well with a large number of paths (O(N) time complexity).
City names are case-sensitive (e.g., 'New York' vs 'new york')	The solution should either be case-sensitive, or a pre-processing step can be added to convert all city names to a uniform case.