Destination City Leetcode Solution

Difficulty Level Easy
Frequently asked in PayPal Yelp
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions StringViews 3696

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.

Destination City Leetcode Solution

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.

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>>();
    paths.add(new ArrayList(Arrays.asList("London","New York")));
    paths.add(new ArrayList(Arrays.asList("New York","Lima")));
    paths.add(new ArrayList(Arrays.asList("Lima","Sao Paulo")));
    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.

Translate ยป