Minimum Index Sum of Two Lists - The Hashtable Trick

Problem is here: https://leetcode.com/problems/minimum-index-sum-of-two-lists/description/

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.

You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.

Example 1:

Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
Output: ["Shogun"]
Explanation: The only restaurant they both like is "Shogun".

Example 2:

Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
Output: ["Shogun"]
Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).

Note:

1. The length of both lists will be in the range of [1, 1000].
2. The length of strings in both lists will be in the range of [1, 30].
3. The index is starting from 0 to the list length minus 1.
4. No duplicates in both lists.

Since the length of the input is relatively small (1000), an N^2 solution might work here. However, this is the classic problem where you want to use a hash table to linearize it:

• Push the content of the first list into a hash table, with an index as the value
• Parse the second list, adding to the hash table accordingly
• Keep track of the min sum of indexes thus far
• On a second loop across the hash table, find the ones that add up to min and push it to the output list (the solution)

Code is below, cheers, Marcelo.

public class Solution
{
 public string[] FindRestaurant(string[] list1, string[] list2)
 {
  if (list1 == null || list1.Length == 0 || list2 == null || list2.Length == 0) return new string[0];

  Hashtable common = new Hashtable();
  int index = 0;
  foreach (string l in list1) common.Add(l, index++);

  int min = Int32.MaxValue;
  foreach (string l in list2)
  {
   if (common.ContainsKey(l))
   {
    common[l] = (int)common[l] + index;
    min = Math.Min(min, (int)common[l]);
   }
   index++;
  }

  LinkedList solList = new LinkedList();
  foreach (string key in common.Keys)
  {
   if ((int)common[key] == min)
   {
    solList.AddLast(key);
   }
  }

  return solList.ToArray();
 }
}