Destination City

Easy

#1328Time: O(N^2), where N is the number of paths. For each of the N paths, we iterate through all N paths again to check if the destination city is also a starting city. String comparisons take time proportional to the string length, but assuming it's bounded by a constant, the complexity is dominated by the nested loops.Space: O(1), as we only use a few variables to keep track of the current candidate and a flag. No extra space proportional to the input size is used.2 companies

Data structures

Array Hash Table String

Companies

Yandex Yelp

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through all possible destination cities and, for each one, checks if it's also a starting city by iterating through all the paths again. A city that is a destination but never a starting point is the final destination.

Algorithm

Iterate through each path p1 in paths. Let the destination of this path be candidate_dest.
Assume candidate_dest is the final destination. We use a boolean flag, say isStartCity, initialized to false.
Start a second, inner loop, iterating through each path p2 in paths. Let the starting city of this path be startCity.
Compare candidate_dest with startCity. If they are the same, it means our candidate is also a starting city. Set isStartCity to true and break the inner loop.
After the inner loop finishes, check the flag isStartCity. If it's still false, it means candidate_dest was never found as a starting city. Thus, it is the final destination. Return candidate_dest.

Walkthrough

The algorithm works by considering each destination city from the paths list as a potential final destination. For each potential destination, we perform a search across all paths to see if this city ever appears as a starting city. If a potential destination is never found as a starting city after checking all paths, it is the true destination city, and we can return it immediately. This method is straightforward but inefficient due to the nested iteration over the list of paths.

1import java.util.List;2 3class Solution {4    public String destCity(List<List<String>> paths) {5        for (List<String> path : paths) {6            String dest = path.get(1);7            boolean isStartCity = false;8            for (List<String> otherPath : paths) {9                if (otherPath.get(0).equals(dest)) {10                    isStartCity = true;11                    break;12                }13            }14            if (!isStartCity) {15                return dest;16            }17        }18        return ""; // Should not be reached given the problem constraints19    }20}

Complexity

Time

O(N^2), where N is the number of paths. For each of the N paths, we iterate through all N paths again to check if the destination city is also a starting city. String comparisons take time proportional to the string length, but assuming it's bounded by a constant, the complexity is dominated by the nested loops.

Space

O(1), as we only use a few variables to keep track of the current candidate and a flag. No extra space proportional to the input size is used.

Trade-offs

Pros

Simple to implement.
Requires no additional memory.

Cons

Inefficient for large inputs due to its quadratic time complexity.

This approach optimizes the search for starting cities by using a hash set. First, we collect all starting cities into a set. Then, we iterate through the paths again and check for a destination city that is not present in our set of starting cities. This city is the final destination.

Algorithm

Create a HashSet<String> called startCities.
Iterate through each path [start, dest] in paths. Add start to the startCities set.
Iterate through each path [start, dest] in paths again.
Check if dest is contained in the startCities set.
If startCities.contains(dest) is false, then dest is the destination city. Return dest.

Walkthrough

The key insight is that the destination city is the only city that appears as a destination but never as a source. We can efficiently check this property using a hash set. The algorithm proceeds in two main steps: first, collect all source cities, and second, find a destination city that is not a source.

1import java.util.HashSet;2import java.util.List;3import java.util.Set;4 5class Solution {6    public String destCity(List<List<String>> paths) {7        Set<String> startCities = new HashSet<>();8        // First pass: collect all starting cities9        for (List<String> path : paths) {10            startCities.add(path.get(0));11        }12        13        // Second pass: find the destination city that is not a starting city14        for (List<String> path : paths) {15            String dest = path.get(1);16            if (!startCities.contains(dest)) {17                return dest;18            }19        }20        21        return ""; // Should not be reached given the problem constraints22    }23}

Complexity

Time

O(N), where N is the number of paths. The first loop to populate the hash set takes O(N) time (assuming average O(1) for set insertion). The second loop to find the destination also takes O(N) time (assuming average O(1) for set lookup). Therefore, the total time complexity is linear.

Space

O(N), where N is the number of paths. In the worst case, all N starting cities are unique and will be stored in the hash set. The space required is proportional to the number of paths and the length of the city names.

Trade-offs

Pros

Significantly faster than the brute-force approach with linear time complexity.
The logic is clear and directly models the problem's condition.

Cons

Requires extra memory to store the set of starting cities.

Solutions

Solution

1class Solution {2public3  String destCity(List<List<String>> paths) {4    Set<String> s = new HashSet<>();5    for (var p : paths) {6      s.add(p.get(0));7    }8    for (var p : paths) {9      if (!s.contains(p.get(1))) {10        return p.get(1);11      }12    }13    return "";14  }15}

1/** * @param {string[][]} paths * @return {string} */ var destCity = function (2  paths,3) {4  const s = new Set();5  for (const [a, _] of paths) {6    s.add(a);7  }8  for (const [_, b] of paths) {9    if (!s.has(b)) {10      return b;11    }12  }13  return "";14};

1class Solution {2public:3  string destCity(vector<vector<string>> &paths) {4    unordered_set<string> s;5    for (auto &p : paths) {6      s.insert(p[0]);7    }8    for (auto &p : paths) {9      if (!s.count(p[1])) {10        return p[1];11      }12    }13    return "";14  }15};

1class Solution:2    def destCity(self, paths: List[List[str]]) -> str: s = {a for a, _ in paths} return next(b for _, b in paths if b not in s)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem