1436. Destination City
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 theset
that stores all the departure cities (cityA
). The use of a set is critical here. Sets in Python store unique elements and they provideO(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 thenext
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) andb
refers to the potential destination cities.- The condition
if b not in s
checks if the cityb
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 thes
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 condition
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 EvaluatorExample 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}
.
- First, we create a set
-
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 sets
. It's in the set, so we move on. - For the second sub-array:
["New York", "Paris"]
,Paris
is checked against the sets
. It's also in the set, so we move on. - For the third sub-array:
["Paris", "Berlin"]
,Berlin
is checked against the sets
. It's not in the set, soBerlin
is our destination city because it clearly has no outgoing flights.
- For the first sub-array:
- Next, we find the destination city using a list comprehension inside the
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 isO(n)
, wheren
is the number of paths since set insertions have an average time complexity ofO(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 ins
. The complexity for the search operation for sets isO(1)
on average. Therefore, this step also has a time complexity ofO(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 containn
elements. This gives us a space complexity ofO(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.
How many ways can you arrange the three letters A, B and C?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!