Problem Description

You are given two arrays of strings list1 and list2. Your task is to find all the common strings with the least index sum.

A common string is any string that appears in both list1 and list2.

For each common string, calculate its index sum by adding its position in list1 (let's call it i) and its position in list2 (let's call it j). The index sum would be i + j.

Among all common strings, you need to find those with the minimum index sum. If multiple common strings have the same minimum index sum, return all of them.

For example:

• If a string appears at list1[2] and list2[3], its index sum is 2 + 3 = 5
• If another string appears at list1[1] and list2[2], its index sum is 1 + 2 = 3
• The second string has a smaller index sum, so it would be preferred

Return all common strings that have the minimum index sum. The order of strings in your answer doesn't matter.

Intuition

To find common strings efficiently, we need a way to quickly check if a string from list1 exists in list2 and get its index. This naturally leads us to think about using a hash table (dictionary) to store all strings from list2 along with their indices. This gives us O(1) lookup time for each string.

Once we have this hash table set up, we can iterate through list1. For each string in list1, we can instantly check if it exists in list2 by looking it up in our hash table. If it exists, we can calculate the index sum i + j where i is the current position in list1 and j is the position we stored in our hash table for list2.

The key insight is that we need to track the minimum index sum found so far. As we iterate through list1, we compare each new index sum with our current minimum:

• If we find a smaller index sum, we reset our answer list to contain only this new string and update our minimum
• If we find an equal index sum to our minimum, we add this string to our existing answer list
• If the index sum is larger, we simply ignore it

This single-pass approach with a hash table gives us an efficient O(n + m) solution where n and m are the lengths of the two lists, avoiding the need for nested loops which would be O(n × m).

Solution Approach

We implement the solution using a hash table to achieve optimal time complexity:

1. Build a hash table for list2: Create a dictionary d that maps each string in list2 to its index. This is done with a dictionary comprehension: d = {s: i for i, s in enumerate(list2)}. This allows O(1) lookup time for any string.

2. Initialize tracking variables:

   • ans = []: An empty list to store the result strings
   • mi = inf: Initialize the minimum index sum to infinity so any valid sum will be smaller

3. Iterate through list1: For each string s at index i in list1:

   • Check if s exists in the hash table d (which means it's also in list2)
   • If it exists, retrieve its index j in list2 using j = d[s]
   • Calculate the index sum: i + j

4. Update the result based on index sum:

   • If i + j < mi: We found a new minimum index sum
     • Update mi = i + j
     • Reset ans = [s] to contain only this string
   • If i + j == mi: We found another string with the same minimum index sum
     • Append this string to the answer: ans.append(s)
   • If i + j > mi: Ignore this string as it doesn't have the minimum index sum

5. Return the result: After processing all strings in list1, return ans which contains all common strings with the minimum index sum.

The time complexity is O(n + m) where n and m are the lengths of list1 and list2 respectively, and the space complexity is O(m) for storing the hash table.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

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

Step 1: Build hash table for list2 We create a dictionary mapping each string in list2 to its index:

d = {"sad": 0, "happy": 1, "good": 2}

Step 2: Initialize tracking variables

ans = []
mi = infinity

Step 3: Iterate through list1

Iteration 1: i = 0, s = "happy"

• Check if "happy" exists in d: Yes, it does!
• Get its index in list2: j = d["happy"] = 1
• Calculate index sum: 0 + 1 = 1
• Compare with mi (infinity): 1 < infinity
• This is a new minimum! Update:
  • mi = 1
  • ans = ["happy"]

Iteration 2: i = 1, s = "sad"

• Check if "sad" exists in d: Yes, it does!
• Get its index in list2: j = d["sad"] = 0
• Calculate index sum: 1 + 0 = 1
• Compare with mi (1): 1 == 1
• Same as minimum! Add to answer:
  • ans = ["happy", "sad"]

Iteration 3: i = 2, s = "good"

• Check if "good" exists in d: Yes, it does!
• Get its index in list2: j = d["good"] = 2
• Calculate index sum: 2 + 2 = 4
• Compare with mi (1): 4 > 1
• Larger than minimum, ignore this string

Step 4: Return result Return ans = ["happy", "sad"]

Both "happy" and "sad" have the minimum index sum of 1, so both are included in the final answer.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m) where n is the length of list1 and m is the length of list2.

• Creating the dictionary d from list2 takes O(m) time as we iterate through all elements in list2 once.
• The main loop iterates through all elements in list1, which takes O(n) time.
• Inside the loop, the dictionary lookup s in d and accessing d[s] both take O(1) average time.
• All other operations inside the loop (comparisons and list operations) take O(1) time.
• Therefore, the total time complexity is O(m) + O(n) = O(n + m).

Space Complexity: O(m) where m is the length of list2.

• The dictionary d stores all elements from list2 as keys with their indices as values, requiring O(m) space.
• The answer list ans can contain at most min(n, m) elements in the worst case (when all common restaurants have the same minimum index sum), which is bounded by O(m).
• Other variables (mi, i, j, s) use O(1) space.
• Therefore, the total space complexity is O(m).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Duplicate Strings in the Same List

One common pitfall is not considering what happens when there are duplicate strings within the same list. While the problem doesn't explicitly state that strings are unique within each list, the solution assumes they are.

Issue Example:

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

If list1 contains duplicates, the dictionary comprehension for list2 would overwrite earlier occurrences, keeping only the last index. Similarly, when iterating through list1, we might process the same string multiple times.

Solution: The current implementation actually handles this correctly for list2 (keeping the last occurrence's index) and processes each position in list1 independently. However, to be explicit about handling duplicates:

def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
    # Use the first occurrence in list2 for consistency
    restaurant_to_index = {}
    for index, restaurant in enumerate(list2):
        if restaurant not in restaurant_to_index:
            restaurant_to_index[restaurant] = index
  
    result = []
    min_index_sum = float('inf')
    seen = set()  # Track processed restaurants
  
    for index1, restaurant in enumerate(list1):
        if restaurant in restaurant_to_index and restaurant not in seen:
            seen.add(restaurant)
            index2 = restaurant_to_index[restaurant]
            current_sum = index1 + index2
          
            if current_sum < min_index_sum:
                min_index_sum = current_sum
                result = [restaurant]
            elif current_sum == min_index_sum:
                result.append(restaurant)
  
    return result

2. Early Termination Optimization Missed

Another pitfall is not recognizing when we can stop searching early. Once we find a common string with index sum k, we don't need to check elements in list1 at index i where i > k because even if they match the first element of list2 (index 0), the sum would be at least i + 0 > k.

Optimized Solution:

def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
    restaurant_to_index = {restaurant: index for index, restaurant in enumerate(list2)}
    result = []
    min_index_sum = float('inf')
  
    for index1, restaurant in enumerate(list1):
        # Early termination: if current index alone exceeds min_sum, stop
        if index1 > min_index_sum:
            break
          
        if restaurant in restaurant_to_index:
            index2 = restaurant_to_index[restaurant]
            current_sum = index1 + index2
          
            if current_sum < min_index_sum:
                min_index_sum = current_sum
                result = [restaurant]
            elif current_sum == min_index_sum:
                result.append(restaurant)
  
    return result

This optimization can significantly improve performance when the minimum index sum is found early in the lists.