Leetcode: Destination City

This question is asked very commonly at Yelp and PayPal.

It is as follows: 

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, which is the city without any path outgoing to another city. It is guaranteed there are no loops, so, there will be exactly one destination city. 

Here's an example:

paths = [["B", "C"], ["D", "B"], ["C", "A"]]

Destination is "A"

All Possible Trips are 

"D" - "B" - "C" - "A"

"B" - "C" - "A"

"C" - "A"

"A"

How can we solve this problem? Simple : we use a hash map.

First, we add the given city to the map and add the destination key to the map. Then we look at every city in a map value, and we return the value that a map city doesn't contain.

Here's the solution:

class Solution {

    if(paths == null || paths.size() == 0) return "";

    //map of to-from cities

    Map<String, String> map = new HashMap<>(); 

    //put from-to path on the map

    for(List<String> path : paths) {

        map.put(path.get(0), path.get(1));

    } 

    //figure out the city with no destination

    for(String city : map.values()) {

        if(!map.containsKey(city)) return city;

    }

    return "";

    }

}