Destination City LeetCode Solution - The Coding Shala

Home >> LeetCode >> Destination City

 In this post, we will learn how to solve LeetCode's Destination City Problem and will implement its solution in Java.

Destination City Problem

You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBi. Return to 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 the "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

Practice this problem on LeetCode(Click Here).

Destination City Java Solution

Approach 1

We can use HashMap to store A, B city as key-value pairs. Then again we will check if city B has any value available on the map or not.

Java Program: 

class Solution {
    public String destCity(List<List<String>> paths) {
        HashMap<String, String> map = new HashMap<>();
        for(int i=0; i<paths.size(); i++) {
            String first = paths.get(i).get(0);
            String second = paths.get(i).get(1);
            map.put(first, second);
        }
        for(int i=0; i<paths.size(); i++) {
            String str = paths.get(i).get(1);
            if(map.containsKey(str)) continue;
            else return str;
        }
        return null;
    }
}

Approach 2

Using set.

First we all the destinations cities into the set then we remove starting cities one by one. 

Java Program: 

class Solution {
    public String destCity(List<List<String>> paths) {
        HashSet<String> set = new HashSet<>();
        for(int i=0; i<paths.size(); i++ ){
            set.add(paths.get(i).get(1));
        }
        
        for(int i=0; i<paths.size(); i++ ){
            set.remove(paths.get(i).get(0));
        }
        
        String dest = set.iterator().next();
        return dest;
    }
}

HashMap method is faster than Set. (Approach 1 is faster).

Other Posts You May Like

• LeetCode - Defanging an IP Address
• LeetCode - Word Subsets
• LeetCode - Friends of Appropriate Ages
• LeetCode - Consecutive Characters
• LeetCode - Kids with the Greatest number of Candies

Please leave a comment below if you like this post or found some errors, it will help me to improve my content.