Find the Destination City

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, 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 the "London" city you will reach the "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

Example 2:

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

Output: "A"

Explanation: All possible trips are: 

"D" -> "B" -> "C" -> "A". 

"B" -> "C" -> "A". 

"C" -> "A". 

"A". 

Clearly the destination city is "A".

Example 3:

Input: paths = [["A","Z"]]

Output: "Z"

Constraints:

1 <= paths.length <= 100

paths[i].length == 2

1 <= cityAi.length, cityBi.length <= 10

cityAi != cityBi

All strings consist of lowercase and uppercase English letters and the space character.

Solution:

using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode.AskGif.Easy.String
{
 class DestCitySoln
 {
 public void execute()
 {
 IList<IList<string>> paths = new List<IList<string>>();
 var path = new List<string>();
 path.Add("B");
 path.Add("C");
 paths.Add(path);

 path = new List<string>();
 path.Add("D");
 path.Add("B");
 paths.Add(path);

 path = new List<string>();
 path.Add("C");
 path.Add("A");
 paths.Add(path);

 var res = DestCity(paths);
 }

 public string DestCity(IList<IList<string>> paths)
 {
 var dict = new Dictionary<string, string>();
 for (int i = 0; i < paths.Count; i++)
 {
 dict.Add(paths[i][0], paths[i][1]);
 }

 string finalDest=null;
 string destination = paths[0][1];
 while(destination != null)
 {
 if (dict.ContainsKey(destination))
 {
 destination = dict[destination];
 }
 else
 {
 finalDest = destination;
 destination = null;
 }
 }

 return finalDest;
 }
 }
}

Time Complexity: O(n) - for one iteration.

Space Complexity: O(n) - for storing in hashmap