Problem Explanation

Andy and Doris are trying to decide on a restaurant to go to for dinner. They each have a list of their favorite restaurants. The goal is to find the restaurant(s) both Andy and Doris like with the smallest index sum, where the index sum is defined as the sum of the indexes of the restaurant in both their lists. If there is more than one restaurant with the smallest index sum, all of those restaurants should be returned.

The input is two arrays of strings, and the output is an array of strings.

Let's walk through a quick example. Let's suppose Andy's favorite restaurants are ["Shogun", "Tapioca Express", "Burger King", "KFC"] and Doris's favorites are ["KFC", "Shogun", "Burger King"]. The restaurants they both like are "Shogun", "Burger King" and "KFC". However, the one with the smallest index sum is "Shogun", with index sum of 1 (its index is 0 in Andy's list and 1 in Doris's list). Thus, "Shogun" is the output.

Solution Approach

One way to solve this problem is to use a hash map to store each restaurant in Andy's list with its index as the value. Then, you iterate over the Doris's list. For each restaurant in Doris's list, check if it exists in the hash map. If it does, calculate the index sum and compare with the current smallest index sum. If the new index sum is smaller, update the smallest index sum, and store the restaurant in an answer list. Otherwise, if the new index sum is equal to the smallest index sum, append the restaurant to the answer list.

The algorithm leverages the fast lookup property of hash maps to quickly find common restaurants and compare index sums.

Python Solution

1
2python
3class Solution:
4    def findRestaurant(self, list1, list2):
5        restaurantToIndex = {}
6        ans = []
7        minSum = float('inf')
8
9        for i in range(len(list1)): 
10            restaurantToIndex[list1[i]] = i
11
12        for i in range(len(list2)): 
13            restaurant = list2[i]
14            if restaurant in restaurantToIndex:
15                sum = restaurantToIndex[restaurant] + i
16                if sum < minSum:
17                    minSum = sum
18                    ans = [restaurant]
19                elif sum == minSum:
20                    ans.append(restaurant)
21
22        return ans

Java Solution

1
2java
3class Solution {
4    public String[] findRestaurant(String[] list1, String[] list2) {
5        HashMap<String, Integer> restaurantToIndex = new HashMap<>();
6        List<String> ans = new ArrayList<>();
7        int minSum = Integer.MAX_VALUE;
8
9        for (int i = 0; i < list1.length; i++)
10            restaurantToIndex.put(list1[i], i);
11
12        for (int i = 0; i < list2.length; i++) {
13            Integer j = restaurantToIndex.get(list2[i]);
14            if (j != null && i + j <= minSum) {
15                if (i + j < minSum) { 
16                    ans.clear();
17                    minSum = i+j;
18                }
19                ans.add(list2[i]);
20            }
21        }
22        
23        return ans.toArray(new String[ans.size()]);
24    }
25}

JavaScript Solution

1
2javascript
3var findRestaurant = function(list1, list2) {
4    let restaurantToIndex = {};
5    let ans = [];
6    let minSum = Infinity;
7
8    list1.forEach((restaurant, index) => {
9        restaurantToIndex[restaurant] = index;
10    })
11
12    list2.forEach((restaurant, index) => {
13        if (restaurant in restaurantToIndex){
14            sum = restaurantToIndex[restaurant] + index;
15            if (sum < minSum){
16                minSum = sum;
17                ans = [restaurant];
18            }
19            else if (sum === minSum) ans.push(restaurant);
20        }
21    });
22
23    return ans;
24};

C++ solution

1
2cpp
3class Solution {
4public:
5    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
6        unordered_map<string, int> restaurantToIndex;
7        vector<string> ans;
8        int minSum = INT_MAX;
9
10        for(int i = 0; i < list1.size(); i++) 
11            restaurantToIndex[list1[i]] = i;
12
13        for(int i = 0; i < list2.size(); i++) {
14            auto it = restaurantToIndex.find(list2[i]);
15            if(it != restaurantToIndex.end()) {
16                int sum = it->second + i;
17                if(sum < minSum) {
18                    minSum = sum;
19                    ans = {list2[i]};
20                } else if(sum == minSum) {
21                    ans.push_back(list2[i]);
22                }
23            }
24        }
25        
26        return ans;
27    }
28};

C# solution

1
2Csharp
3public class Solution {
4    public string[] FindRestaurant(string[] list1, string[] list2) {
5        Dictionary<string, int> restaurantToIndex = new Dictionary<string, int>();
6        List<string> ans = new List<string>();
7        int minSum = Int32.MaxValue;
8
9        for (int i = 0; i < list1.Length; i++)
10            restaurantToIndex[list1[i]] = i;
11
12        for (int i = 0; i < list2.Length; i++) {
13            if (restaurantToIndex.ContainsKey(list2[i])){
14                int sum = i + restaurantToIndex[list2[i]];
15                if (sum < minSum){
16                    minSum = sum;
17                    ans.Clear();
18                    ans.Add(list2[i]);
19                } else if (sum == minSum){
20                    ans.Add(list2[i]);
21                }
22            }
23        }
24
25        return ans.ToArray();
26    }
27}

These solutions show how to effectively solve the problem using a common approach in various mainstream programming languages. All of these solutions use a hashmap to store the index of each of Andy's favorite restaurants, then iterate over the Doris's list checking if each restaurant also appears in Andy's list via quick hashmap lookups.

In each solution, the code keeps track of the minimum index sum seen so far and the restaurant(s) with that index sum. If it finds a restaurant with a smaller index sum, it updates the minimum index sum and replaces the list of restaurants. If it finds a restaurant with an equal index sum, it adds that restaurant to the list.

The complexity of these solutions is O(n), with n being length of longer list. This is because we simply iterate over each list once, and hashmap operations (insertion, retrieval, and checking for existence) are on average a constant time complexity.

One key take-away from these solutions is use of hashmap for efficient search operations over a huge dataset and to remember a certain property (here, index of restaurant). Another important point is that given the favorite restaurant lists can be large, having a solution with linear time complexity is crucial to ensure timely execution.

Remember, even though the problem might seem to require finding intersection of two lists, it actually required more information (sum of indices). Therefore, a hashmap storing restaurants with their indices was the key idea here.