599. Minimum Index Sum of Two Lists

Problem

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.

Problem Summary

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 the restaurants they both like with the smallest index sum. If there is more than one answer, output all answers without considering order. You can assume that an answer always exists.

Note:

• The lengths of both lists are in the range of [1, 1000].
• The lengths of strings in both lists are in the range of [1, 30].
• Indices start from 0 and go to the list length minus 1.
• Neither list has duplicate elements.

Solution Approach

• Andy and Doris each have their own list of favorite restaurants. The task is to find a restaurant they both like; if there are multiple with the same number of common likes, output them all. This is an easy problem: use a map to count frequencies, and output the restaurant with the highest frequency.

Code

package leetcode

func findRestaurant(list1 []string, list2 []string) []string {
	m, ans := make(map[string]int, len(list1)), []string{}
	for i, r := range list1 {
		m[r] = i
	}
	for j, r := range list2 {
		if _, ok := m[r]; ok {
			m[r] += j
			if len(ans) == 0 || m[r] == m[ans[0]] {
				ans = append(ans, r)
			} else if m[r] < m[ans[0]] {
				ans = []string{r}
			}
		}
	}
	return ans
}