Minimum Index Sum of Two Lists

Difficulty: Easy | Acceptance: 59.80% | Paid: No Topics: Array, Hash Table, String

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.

• Examples
• Constraints
• Approach 1: Hash Map
• Approach 2: Brute Force

Examples

Example 1

Input:

list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]

Output:

["Shogun"]

Explanation: The only common string is “Shogun”.

Example 2

Input:

list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"]

Output:

["Shogun"]

Explanation: The common string with the least index sum is “Shogun” with index sum = (0 + 1) = 1.

Example 3

Input:

list1 = ["happy","sad","good"], list2 = ["sad","happy","good"]

Output:

["sad","happy"]

Explanation: There are three common strings: “happy” with index sum = (0 + 1) = 1. “sad” with index sum = (1 + 0) = 1. “good” with index sum = (2 + 2) = 4. The strings with the least index sum are “sad” and “happy”.

Constraints

1 <= list1.length, list2.length <= 1000
The sum of lengths of list1 and list2 will not exceed 1000.
0 <= list1[i].length, list2[i].length <= 30
list1[i] and list2[i] consist of spaces ' ' and English letters.
All the strings of list1 are unique.
All the strings of list2 are unique.

Approach 1: Hash Map

Intuition To efficiently find common strings and their indices, we can store the indices of the first list in a hash map. Then, we iterate through the second list, checking for common strings and calculating the index sum on the fly.

Steps

• Create a hash map to store each string from list1 as a key and its index as the value.
• Initialize minSum to infinity and an empty list result.
• Iterate through list2 with index j.
• If the current string exists in the hash map, calculate the sum of the stored index and j.
• If this sum is less than minSum, update minSum and reset result with the current string.
• If the sum equals minSum, append the current string to result.
• Return result.

from typing import List

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        index_map = {s: i for i, s in enumerate(list1)}
        min_sum = float('inf')
        result = []
        
        for j, s in enumerate(list2):
            if s in index_map:
                curr_sum = index_map[s] + j
                if curr_sum < min_sum:
                    min_sum = curr_sum
                    result = [s]
                elif curr_sum == min_sum:
                    result.append(s)
        return result

Complexity

• Time: O(N + M), where N and M are the lengths of list1 and list2. We traverse each list once.
• Space: O(N), to store the hash map for list1.
• Notes: This is the optimal solution for this problem.

Approach 2: Brute Force

Intuition Compare every string in the first list with every string in the second list. If they match, calculate the sum of their indices and track the minimum sum found.

Steps

• Initialize minSum to infinity and an empty list result.
• Iterate through list1 with index i.
• Iterate through list2 with index j.
• If list1[i] equals list2[j]:
  • Calculate sum = i + j.
  • If sum < minSum, update minSum and set result to [list1[i]].
  • If sum == minSum, append list1[i] to result.
• Return result.

from typing import List

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        min_sum = float('inf')
        result = []
        
        for i, s1 in enumerate(list1):
            for j, s2 in enumerate(list2):
                if s1 == s2:
                    curr_sum = i + j
                    if curr_sum < min_sum:
                        min_sum = curr_sum
                        result = [s1]
                    elif curr_sum == min_sum:
                        result.append(s1)
        return result

Complexity

• Time: O(N * M), where N and M are the lengths of list1 and list2. In the worst case, we check every pair.
• Space: O(1), excluding the space required for the output list.
• Notes: This approach is simple but inefficient for large inputs compared to the hash map approach.