Destination City

You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBi.

Find the destination city, that is, the city without any path outgoing to another city.

Example 1:

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo"

Approach

Java

import java.util.ArrayList;
import java.util.List;

public class DestinationCity {
    public static void main(String[] args) {
        String[][] paths = { { "London", "New York" }, { "New York", "Lima" },
             { "Lima", "Sao Paulo" } };
        System.out.println(destCity(paths));
    }

    static String destCity(String[][] paths) {
        List<String> st = new ArrayList<String>();
        int n = paths.length;
        for (int i = 0; i < n; i++)
            st.add(paths[i][0]);
        String res = null;
        for (int i = 0; i < n; i++) {
            if (!st.contains(paths[i][1])) {
                res = paths[i][1];
                break;
            }
        }
        return res;
    }
}

C++

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

string destCity(vector<vector<string>> &paths)
{
    set<string> st;
    int n = paths.size();
    for (int i = 0; i < n; i++)
        st.insert(paths[i][0]);
    string res;
    for (int i = 0; i < n; i++)
    {
        if (st.find(paths[i][1]) == st.end())
        {
            res = paths[i][1];
            break;
        }
    }
    return res;
}

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

    cout << destCity(paths);
    return 0;
}