# Destination City Leetcode Solution

Difficulty Level Easy
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions String

The problem Destination City Leetcode Solution provides us with some relations between cities. The input is given as line separated pair of cities. Each line in input denotes a direct road from the starting point to the endpoint. It is given in the problem, that the cities do not form a circular route. It is also stated that the input has a destination city. A destination city is defined as a city that does not have any outgoing road. So as usual before diving deep into the solution, let’s take a look at a few examples.

`paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]`
`Sao Paulo`

Explanation: So if we go by the input, London has a direct road to New York. New York has a direct road to Lima. In the end, Lima has a direct road to Sao Paulo. So, the destination city must be Sao Paulo because it has no outgoing roads.

`paths = [["A","Z"]]`
`Z`

Explanation: We have a single direct road starting from A to Z. Thus Z is our destination city.

## Approach to Destination City Leetcode Solution

The problem Destination City Leetcode Solution asked us to find the destination. The input has provided us with some direct roads among the cities. It is given that a destination city does not have an outgoing road. The problem can be easily solved using a hashmap. In the hashmap, we keep track of outgoing roads. We traverse the paths vector and increment the number of outgoing roads of the cities. Then afterward we check if there is any city among the paths vector, that does not have an outgoing road. We return that city as the answer.

House Robber II Leetcode Solution

## Code for Destination City Leetcode Solution

### C++ code

```#include <bits/stdc++.h>
using namespace std;

string destCity(vector<vector<string>>& paths) {
unordered_map<string, int> outdegree;
for(auto x: paths){
outdegree[x[0]]++;
}
for(auto x: paths)
if(outdegree[x[0]] == 0)
return x[0];
else if(outdegree[x[1]] == 0)
return x[1];
return paths[0][0];
}

int main(){
vector<vector<string>> paths = {{"London","New York"},{"New York","Lima"},{"Lima","Sao Paulo"}};
string output = destCity(paths);
cout<<output;
}
```
`Sao Paulo`

### Java code

```import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
public static String destCity(List<List<String>> paths) {
HashMap<String, Integer> outdegree = new HashMap<String, Integer>();
for(List<String> x: paths)
if(outdegree.containsKey(x.get(0)))
outdegree.put(x.get(0), outdegree.get(x.get(1))+1);
else
outdegree.put(x.get(0), 1);

for(List<String> x: paths)
if(!outdegree.containsKey(x.get(0)))
return x.get(0);
else if(!outdegree.containsKey(x.get(1)))
return x.get(1);

return paths.get(0).get(0);
}

public static void main (String[] args) throws java.lang.Exception{
List<List<String>> paths = new ArrayList<List<String>>();
System.out.print(destCity(paths));
}
}```
`Sao Paulo`

## Complexity Analysis

### Time Complexity

O(N), since we used Hashmap, the time complexity is reduced to linear.

### Space Complexity

O(N), space is required to store the number of outgoing roads in the hashmap. Thus the space complexity is also linear.