Minimum Index Sum Of Two Lists - Leetcode Solution

Problem Statement

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:

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".

Solution

The problem is asking us to find the minimum index sum of two lists and output the common interest. Since we need to minimize the index sum, it makes sense to use a hash map to store the index of each restaurant in the first list. Then, we can iterate through the second list and check if the restaurant is in the first list. If it is, we calculate the index sum and keep track of the minimum index sum seen so far. Finally, we iterate through the hash map and output all the restaurants with the minimum index sum.

Here is the code implementation of this solution:

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        # create a hash map of restaurant indices in the first list
        hash_map = {}
        for i in range(len(list1)):
            hash_map[list1[i]] = i

        min_index_sum = float('inf')  # initialize the minimum index sum
        result = []  # initialize the result list

        # iterate through the second list
        for j in range(len(list2)):
            if list2[j] in hash_map:
                # calculate the index sum
                index_sum = j + hash_map[list2[j]]
                if index_sum < min_index_sum:
                    # if it's smaller than the minimum so far, reset the result list and update the minimum index sum
                    result = [list2[j]]
                    min_index_sum = index_sum
                elif index_sum == min_index_sum:
                    # if it's equal to the minimum so far, append the restaurant to the result list
                    result.append(list2[j])

        return result

Time Complexity

The time complexity of this solution is O(m+n), where m and n are the lengths of the two input lists. This is because we need to iterate through both lists once to create the hash map and check if restaurants exist in the first list. The worst case scenario is that we iterate through both lists once without finding any common interest.

Space Complexity

The space complexity of this solution is O(m), where m is the length of the first input list. This is because we store the index of each restaurant in the first list in a hash map. The size of the hash map is proportional to the length of the first list.

1