Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

599. Minimum Index Sum of Two Lists - Leetcode Solution

Code Implementation

class Solution:
    def findRestaurant(self, list1, list2):
        index_map = {restaurant: idx for idx, restaurant in enumerate(list1)}
        min_sum = float('inf')
        result = []
        for idx2, restaurant in enumerate(list2):
            if restaurant in index_map:
                idx1 = index_map[restaurant]
                total_idx = idx1 + idx2
                if total_idx < min_sum:
                    min_sum = total_idx
                    result = [restaurant]
                elif total_idx == min_sum:
                    result.append(restaurant)
        return result
      
class Solution {
public:
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        unordered_map<string, int> index_map;
        for (int i = 0; i < list1.size(); ++i) {
            index_map[list1[i]] = i;
        }
        int min_sum = INT_MAX;
        vector<string> result;
        for (int j = 0; j < list2.size(); ++j) {
            if (index_map.count(list2[j])) {
                int total = index_map[list2[j]] + j;
                if (total < min_sum) {
                    min_sum = total;
                    result.clear();
                    result.push_back(list2[j]);
                } else if (total == min_sum) {
                    result.push_back(list2[j]);
                }
            }
        }
        return result;
    }
};
      
class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        Map<String, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < list1.length; i++) {
            indexMap.put(list1[i], i);
        }
        int minSum = Integer.MAX_VALUE;
        List<String> result = new ArrayList<>();
        for (int j = 0; j < list2.length; j++) {
            if (indexMap.containsKey(list2[j])) {
                int total = indexMap.get(list2[j]) + j;
                if (total < minSum) {
                    minSum = total;
                    result.clear();
                    result.add(list2[j]);
                } else if (total == minSum) {
                    result.add(list2[j]);
                }
            }
        }
        return result.toArray(new String[result.size()]);
    }
}
      
var findRestaurant = function(list1, list2) {
    const indexMap = {};
    for (let i = 0; i < list1.length; i++) {
        indexMap[list1[i]] = i;
    }
    let minSum = Number.MAX_SAFE_INTEGER;
    let result = [];
    for (let j = 0; j < list2.length; j++) {
        if (indexMap.hasOwnProperty(list2[j])) {
            let total = indexMap[list2[j]] + j;
            if (total < minSum) {
                minSum = total;
                result = [list2[j]];
            } else if (total === minSum) {
                result.push(list2[j]);
            }
        }
    }
    return result;
};

Problem Description

Given two lists of strings, list1 and list2, representing favorite restaurants of two people, your task is to find all common restaurants with the least sum of their indices in both lists. If there are multiple answers with the same minimum index sum, return all of them in any order. Each restaurant name is unique within each list, and you should not reuse elements.

Thought Process

To solve this problem, the straightforward approach would be to compare every restaurant in list1 with every restaurant in list2, tracking the index sums for matches. However, this brute-force method is inefficient, especially for large lists, since it checks every possible pair. To optimize, we can utilize a hash map (dictionary) to store the indices of restaurants in one list for quick lookup. This way, for each restaurant in the second list, we can instantly check if it's in the first list and calculate the index sum. By tracking the minimum sum found, we can build our result efficiently.

Solution Approach

The optimized solution uses a hash map for fast lookups and efficient computation. Here’s how you can approach it step-by-step:
  1. Build a Hash Map:
    • Iterate through list1 and store each restaurant name as a key and its index as the value in a hash map.
  2. Iterate Through list2:
    • For each restaurant in list2, check if it exists in the hash map (i.e., is also present in list1).
    • If it exists, calculate the sum of indices from both lists.
  3. Track Minimum Index Sum:
    • Maintain a variable to store the minimum index sum found so far.
    • If a new lower sum is found, update this variable and reset the result list to just this restaurant.
    • If another restaurant has the same minimum sum, add it to the result list.
  4. Return the Result:
    • After iterating, return the list of restaurants with the minimum index sum.
Using a hash map ensures that lookups are O(1), making the overall solution efficient and scalable.

Example Walkthrough

Let's walk through an example for clarity:
  • list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]
  • list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
  1. Build a hash map from list1:
    • "Shogun": 0
    • "Tapioca Express": 1
    • "Burger King": 2
    • "KFC": 3
  2. Iterate through list2:
    • Index 0: "Piatti" (not in hash map)
    • Index 1: "The Grill at Torrey Pines" (not in hash map)
    • Index 2: "Hungry Hunter Steakhouse" (not in hash map)
    • Index 3: "Shogun" (found in hash map at index 0)
    The index sum for "Shogun" is 0 (from list1) + 3 (from list2) = 3.
  3. Since "Shogun" is the only common restaurant, and its index sum is the minimum, return ["Shogun"].

Time and Space Complexity

  • Brute-force approach:
    • Time Complexity: O(N x M), where N and M are the lengths of list1 and list2. This is because you compare every pair of elements.
    • Space Complexity: O(1) extra space, aside from the result list.
  • Optimized approach (using hash map):
    • Time Complexity: O(N + M). Building the hash map takes O(N), and iterating through list2 takes O(M), with constant-time lookups.
    • Space Complexity: O(N) for the hash map storing indices from list1.
The optimized solution is much faster and uses extra space for the hash map, which is a good trade-off for efficiency.

Summary

This problem demonstrates how hash maps can transform a brute-force search into an efficient solution. By storing one list's indices in a hash map, we can quickly check for common restaurants and calculate index sums. The result is a clean, fast, and scalable approach that is easy to understand and implement.