Destination City
EasyPrompt
You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBi. 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 <= 100paths[i].length == 21 <= cityAi.length, cityBi.length <= 10cityAi != cityBi- 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
p1inpaths. Let the destination of this path becandidate_dest. - Assume
candidate_destis the final destination. We use a boolean flag, sayisStartCity, initialized tofalse. - Start a second, inner loop, iterating through each path
p2inpaths. Let the starting city of this path bestartCity. - Compare
candidate_destwithstartCity. If they are the same, it means our candidate is also a starting city. SetisStartCitytotrueand break the inner loop. - After the inner loop finishes, check the flag
isStartCity. If it's stillfalse, it meanscandidate_destwas never found as a starting city. Thus, it is the final destination. Returncandidate_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.
import java.util.List; class Solution { public String destCity(List<List<String>> paths) { for (List<String> path : paths) { String dest = path.get(1); boolean isStartCity = false; for (List<String> otherPath : paths) { if (otherPath.get(0).equals(dest)) { isStartCity = true; break; } } if (!isStartCity) { return dest; } } return ""; // Should not be reached given the problem constraints }}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.
Solutions
Solution
class Solution {public String destCity(List<List<String>> paths) { Set<String> s = new HashSet<>(); for (var p : paths) { s.add(p.get(0)); } for (var p : paths) { if (!s.contains(p.get(1))) { return p.get(1); } } return ""; }}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.