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
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to Create a Simple Calculator - The Coding Shala

N-th Tribonacci Number Solution - The Coding Shala

Java Program to Convert Binary to Decimal - The Coding Shala

LeetCode - Shuffle the Array Solution - The Coding Shala

Introduction to Kotlin Programming Language for Backend Development - The Coding Shala