1436. Destination City

EasyHash TableString

Problem Description

You're presented with an array called paths, where each element is itself an array of two cities, cityA and cityB. The sub-array [cityA, cityB] signifies that there is a direct path from cityA to cityB. Your task is to determine the destination city. The destination city is defined as the city that doesn't have any outgoing paths to other cities. Hence, it only appears as the second element in one of the sub-arrays and never as the first element. Given the graph of paths forms a straight line, meaning that it doesn’t loop back on itself, you can be certain there is only one destination city.

Intuition

For the solution, a set called s is created to hold all the cities that have outgoing paths; these are the first elements (cityA) in each sub-array of paths. Since the graph is guaranteed to be linear without loops, the destination city will never appear as a cityA. With this knowledge, the solution iterates over the paths again, checking the second element of each sub-array (cityB) to see if it doesn't exist in the set s. If cityB isn't in s, that means it has no outgoing paths and is thus the destination city. This result is then returned. Using a set for s is efficient as it allows for constant time complexity checks for the presence of a city in the set.

Solution Approach

The implementation of the solution involves the use of a Python set data structure and list comprehension, both of which are efficient in their respective roles.

Python Set: The line s = {a for a, _ in paths} initiates the set that stores all the departure cities (cityA). The use of a set is critical here. Sets in Python store unique elements and they provide O(1) average time complexity for checking the presence or absence of an item. Since we only care about whether a city has outgoing paths, the set allows us to efficiently track cities we've seen as departure points.
List Comprehension: The line return next(b for _, b in paths if b not in s) uses a list comprehension combined with the next function to find the destination city. This works by iterating over each path, _ is used to ignore the first element (since we're not interested in the departure cities anymore) and b refers to the potential destination cities.
- The condition if b not in s checks if the city b is not in the set of departure cities we created earlier. Since the destination city will not have an outgoing path, it will not be found in the s set.
- We use the next iterator function to immediately return the first occurrence of such a city. This improves efficiency because it stops the iteration as soon as the condition is met, and we don't have to check the rest of the paths.

The combination of a set for quick look-ups and an iterator for early exit provides a neat and efficient approach to solving this problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a small example to illustrate the solution approach: Imagine we have the following paths array:

paths = [["London", "New York"], ["New York", "Paris"], ["Paris", "Berlin"]]

Here, each sub-array represents a direct flight path from one city to another. By examining the data, we need to find out which city is our final destination (a city with no outgoing flights).

Creating a Set of Departure Cities:
- First, we create a set s to keep track of all departure cities (cities with outgoing flights), which would be {"London", "New York", "Paris"} in our example. This set is created using a set comprehension: s = {a for a, _ in paths}.
Finding the Destination City:
- Next, we find the destination city using a list comprehension inside the next function: return next(b for _, b in paths if b not in s).
- The list comprehension iterates over the paths:
  - For the first sub-array: ["London", "New York"], New York is checked against the set s. It's in the set, so we move on.
  - For the second sub-array: ["New York", "Paris"], Paris is checked against the set s. It's also in the set, so we move on.
  - For the third sub-array: ["Paris", "Berlin"], Berlin is checked against the set s. It's not in the set, so Berlin is our destination city because it clearly has no outgoing flights.

Since Berlin is not in the set of departure cities, it is immediately returned by the next function as the destination city. There is no need to check further. Thus, the answer to our example would be "Berlin".

This approach is highly efficient because it avoids checking the entire array for the destination city and makes a quick determination using the set.

Solution Implementation

1class Solution:
2    def destCity(self, paths: List[List[str]]) -> str:
3        # Create a set of departure cities
4        departures = {path[0] for path in paths}
5      
6        # Iterate through each pair of cities in paths
7        for _, destination in paths:
8            # If the destination city is not in the set of departures
9            if destination not in departures:
10                # It must be the destination city we are looking for, return it
11                return destination
12
13# The `paths` parameter is expected to be a list where each element is another list
14# of two strings, representing a departure city and a destination city, respectively.
15
16# The `destCity` method will return the name of the city that is the destination city.
17# A destination city is defined as one that is not a departure city for any city-path
18# within the 'paths' list. In other words, it has no outgoing paths.
19```
20
21In this rewritten code, I have:
22
231. Followed the Python style guide (PEP 8) for variable naming by renaming the variable `s` to `departures` to make its purpose clearer.
242. I have replaced the set comprehension with a more standard loop format that should be easier for many programmers to understand.
253. I've included comments that describe the logic of the code block and the purpose of variables and methods.
26
27Note that Python's 'typing' module needs to be imported to use type hints like `List`:
28
29```python
30from typing import List
31

1class Solution {
2    public String destCity(List<List<String>> paths) {
3        // Create a HashSet to store all departure cities
4        Set<String> departureCities = new HashSet<>();
5      
6        // Iterate over the list of paths and add all starting cities to the HashSet
7        for (List<String> path : paths) {
8            departureCities.add(path.get(0));
9        }
10      
11        // Iterate over the list of paths to find the destination city
12        // The destination city will not be found in the set of departure cities
13        for (List<String> path : paths) {
14            if (!departureCities.contains(path.get(1))) {
15                // We found the destination city, return it
16                return path.get(1);
17            }
18        }
19      
20        // If no unique destination city is found, return an empty string
21        return "";
22    }
23}
24

1#include <vector>
2#include <string>
3#include <unordered_set>
4
5class Solution {
6public:
7    // Function to find the destination city from a list of paths.
8    // Each path is represented as a vector of two strings, where the first string is the starting city and the second is the destination city.
9    string destCity(vector<vector<string>>& paths) {
10        // Create an unordered set to store the starting cities.
11        unordered_set<string> startingCities;
12
13        // Populate the startingCities set with starting cities from the paths.
14        for (auto& path : paths) {
15            startingCities.insert(path.front()); // The starting city is at the front of each path.
16        }
17
18        // Loop through the paths again and identify the destination city that is not in the startingCities set.
19        // This city is the final destination, since no paths originate from it.
20        for (auto& path : paths) {
21            // If the destination city in the current path is not found in the startingCities set,
22            // it means we have found the destination city.
23            if (startingCities.count(path.back()) == 0) { // The destination city is at the back of each path.
24                return path.back();
25            }
26        }
27
28        // If all cities appear as a starting city, return an empty string.
29        // This scenario shouldn't happen according to the problem's constraints but is used as a safe guard.
30        return "";
31    }
32};
33

1// This function finds the destination city from a list of origin-destination path pairs.
2// paths: A list of pairs where each pair contains the origin and destination city names.
3function destCity(paths: string[][]): string {
4    // Create a Set to store just the origin cities for quick lookup.
5    const originCities = new Set<string>();
6
7    // Populate the Set with just the first element (origin) from each path.
8    paths.forEach(path => {
9        const origin = path[0];
10        originCities.add(origin);
11    });
12
13    // Iterate over the paths to find a city that is not an origin city.
14    for (const path of paths) {
15        const destination = path[1];
16        // If the current city is not in the set of origin cities, it's our destination.
17        if (!originCities.has(destination)) {
18            return destination;
19        }
20    }
21
22    // If all cities are found as origins, there's no destination city which should not happen.
23    // Return an empty string (this case is assumed to not occur as per the problem statement).
24    return '';
25}
26

Time and Space Complexity

The given Python code defines a method destCity to find the destination city from a list of city paths. A path is represented by a list of two strings, where the first string is the starting city and the second is the destination city. We want to find the destination city that is not the starting point of any path.

Time Complexity

The time complexity of the code can be determined by looking at the operations performed:

Creating a set s of starting cities: This operation traverses the list of paths once. The time complexity of this operation is O(n), where n is the number of paths since set insertions have an average time complexity of O(1) per insertion.
Finding the destination city which is not in the starting cities set s: This involves another traversal through the paths list. For each destination city, we check whether it is not in s. The complexity for the search operation for sets is O(1) on average. Therefore, this step also has a time complexity of O(n).

Since these operations are sequential, the overall time complexity of the code is O(n).

Space Complexity

The space complexity is based on the additional memory used by the code:

A set s created to store starting cities. In the worst-case scenario, all cities are unique, and hence, s would contain n elements. This gives us a space complexity of O(n).

There are no other significant data structures utilized. Thus, the total space complexity of the method is O(n).

In summary:

Time Complexity: O(n)
Space Complexity: O(n)

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know