Minimum Index Sum of Two Lists - The Hashtable Trick
Problem is here: https://leetcode.com/problems/minimum-index-sum-of-two-lists/description/
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:
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:
- The length of both lists will be in the range of [1, 1000].
- The length of strings in both lists will be in the range of [1, 30].
- The index is starting from 0 to the list length minus 1.
- 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)
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();
}
}
Comments
Neat, I've decided to keep a list of best candidates instead:
Reply Deleteclass Solution {
public:
vector findRestaurant(vector& list1, vector& list2) {
unordered_map index2;
for (int i = 0; i < list2.size(); ++i) index2[list2[i]] = i;
vector result;
int min_sum = numeric_limits::max();
for (int i = 0; i < list1.size(); ++i) {
auto it = index2.find(list1[i]);
if (it == index2.cend()) continue;
int current_sum = it->second + i;
if (current_sum > min_sum) continue;
if (current_sum < min_sum) {
result.clear();
min_sum = current_sum;
}
result.push_back(i);
}
vector restaurants; restaurants.reserve(result.size());
for (int idx : result) restaurants.push_back(list1[idx]);
return restaurants;
}
};
Cheers,
Taras
Post a Comment
[γγ¬γΌγ ]