599. Minimum Index Sum of Two Lists
Model: qwen2.5-coder:14b
Topics: Hash Table
FAANG asked: 0
Acceptance rate: 51.9%
Problem Breakdown
The problem requires finding common restaurants between two lists with the minimum index sum. The input consists of two lists of restaurant names, and the output should be the list(s) of common restaurants that have the smallest combined index from both lists. If there are multiple such restaurants, all should be returned.
Inputs:
list1: A list of restaurant names.list2: Another list of restaurant names.
Outputs:
- A list of restaurant names that appear in both
list1andlist2, with the smallest combined index sum.
Implicit Constraints/Edge Cases:
- The lists can be empty, but since it’s guaranteed there is always an answer, this case won’t occur.
- All strings in each list are unique.
- Strings may contain spaces and English letters.
Intuition
A brute-force approach would involve checking every pair of restaurants from both lists to see if they match and calculate their index sums. This approach has a time complexity of O(n * m), where n and m are the lengths of list1 and list2, respectively, which is inefficient for larger lists.
The key insight is to use a hash table (dictionary) to store the indices of one list, allowing us to quickly look up the index of any restaurant in the other list. This reduces the time complexity to O(n + m), where n and m are the lengths of list1 and list2.
Approach
- Create a Hash Table: Store the restaurants from
list1as keys with their indices as values. - Initialize Variables: Set up variables to keep track of the minimum index sum found so far and a list to store the result.
- Iterate Through
list2:- For each restaurant in
list2, check if it exists in the hash table. - If it does, calculate the combined index sum.
- If this sum is less than the current minimum, update the minimum and reset the result list with this restaurant.
- If the sum equals the current minimum, add this restaurant to the result list.
- For each restaurant in
- Return the Result List: After iterating through
list2, return the list of restaurants with the minimum index sum.
Complexity Analysis
- Time Complexity: O(n + m), where n is the length of
list1and m is the length oflist2. We iterate through both lists once. - Space Complexity: O(min(n, m)), for storing the hash table. In the worst case, we store all elements from one list.
Solution
def findRestaurant(list1, list2):
# Step 1: Create a hash table to store indices of list1
index_map = {restaurant: i for i, restaurant in enumerate(list1)}
# Step 2: Initialize variables to track the minimum index sum and result list
min_index_sum = float('inf')
result = []
# Step 3: Iterate through list2
for j, restaurant in enumerate(list2):
if restaurant in index_map:
current_index_sum = index_map[restaurant] + j
if current_index_sum < min_index_sum:
min_index_sum = current_index_sum
result = [restaurant]
elif current_index_sum == min_index_sum:
result.append(restaurant)
# Step 4: Return the result list
return result
Edge Cases Handled
- Common Restaurants with Different Index Sums: The algorithm correctly identifies and returns only those restaurants with the smallest index sum.
- Multiple Restaurants with the Same Minimum Index Sum: All such restaurants are included in the result list.
- No Common Restaurants (though not applicable as per problem statement): If there were no common restaurants, the hash table lookup would fail, and the result list would remain empty.