We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Index Sum of Two Lists

Number: 599

Difficulty: Easy

Paid? No

Companies: Yelp

Problem Description

Given two lists of unique strings, list1 and list2, find all common strings that have the smallest sum of their indices in both lists. A common string is one that appears in both lists. If there are multiple common strings with the same minimum index sum, return all of them.

Key Insights

  • Use a hash table (or dictionary) to map strings from the first list to their indices.
  • Traverse the second list and for every string that exists in the hash table, compute the sum of indices.
  • Keep track of the minimum index sum and update the result list accordingly.
  • Since every string in both lists is unique, there's no need to handle duplicates.
  • The approach visits each element in both lists only once.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of list1 and m is the length of list2. Space Complexity: O(n), due to the additional hash table storage for list1.

Solution

The solution involves creating a hash table for list1 that maps each string to its index. Next, we iterate over list2, checking if the current string exists in the hash table. If it does, we compute the index sum by adding the index from list2 and the stored index from list1. We then compare this sum with the minimum sum found so far:

  • If the sum is less than the current minimum, update the minimum index sum and reset the result list with this string.
  • If the sum equals the current minimum, simply append the string to the result list.

This ensures that by the end, the result list contains all common strings with the minimum index sum.

Code Solutions

# Python solution for Minimum Index Sum of Two Lists

def findRestaurant(list1, list2):
    # Create a dictionary to store string to index mapping for list1
    index_map = {restaurant: idx for idx, restaurant in enumerate(list1)}
    min_sum = float('inf')  # Initialize the minimum index sum as infinity
    result = []  # List to store restaurants with the minimum index sum
    
    # Iterate over list2 with index tracking
    for idx2, restaurant in enumerate(list2):
        # Check if the restaurant exists in list1 using the dictionary
        if restaurant in index_map:
            idx1 = index_map[restaurant]
            current_sum = idx1 + idx2  # Calculate the index sum
            # If a smaller index sum is found, update min_sum and reset result list
            if current_sum < min_sum:
                min_sum = current_sum
                result = [restaurant]
            # If the same index sum is found, append the restaurant to the result list
            elif current_sum == min_sum:
                result.append(restaurant)
    return result

# Example usage:
list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]
list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
print(findRestaurant(list1, list2))  # Output: ["Shogun"]
← Back to All Questions