Leetcode problem 70 - 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 “London” city you will reach “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”

/**
 * @param {string[][]} paths
 * @return {string}
 */
var destCity = function (paths) {
  // create a hash table to store the paths
  let hash = {};
  // create a pointer to iterate through the paths
  let pointer = 0;

  // store the paths in the hash table
  for (const path of paths) {
    // store the paths in the hash table
    hash[path[0]] = path[1];
  }

  // iterate through the paths
  while (pointer !== paths.length) {
    // store the next city
    let nextCity = paths[pointer][1];
    console.log(nextCity);
    // if the next city is not in the hash table
    if (!hash[nextCity]) {
      // return the next city
      return paths[pointer][1];
    }
    // update the pointer
    pointer++;
  }
};

The time complexity of the given code is O(n), where n is the number of paths in the input array. The function initializes a hash table (hash) to store the mappings of starting cities to their corresponding destination cities. It then iterates through the paths array to populate the hash table. Subsequently, the function uses a while loop that continues until the pointer reaches the end of the paths array. In each iteration, it retrieves the next city based on the current pointer position and checks if it is not found in the hash table. If the next city is not in the hash table, it means that it is the destination city, and the function returns this city. The loop iterates through at most n paths, resulting in a time complexity of O(n).