1. Minimum Index Sum of Two Lists (LeetCode)
Model answer
The task
Given two lists of strings, return every string that appears in both lists and has the smallest sum of its positions across the two lists. If several strings tie for the minimum, include all of them.
Key idea
Store each string’s position in the first list in a hash table. Scan the second list once, computing the position sum for each shared string and keeping track of the smallest sum seen so far.
Approach
- Build a map from strings in the first list to their positions.
- Initialize the best position sum and an empty result list.
- Scan the second list with its positions.
- For each shared string, calculate the position sum.
- Replace the result when the sum is smaller; append when it ties.
class Solution:
def findRestaurant(self, list1: list[str], list2: list[str]) -> list[str]:
# Map each string to its position in the first list.
first_index = {name: i for i, name in enumerate(list1)}
best_sum = float("inf")
result = []
# Check shared strings and track all minimum-sum ties.
for j, name in enumerate(list2):
if name not in first_index:
continue
index_sum = first_index[name] + j
if index_sum < best_sum:
best_sum = index_sum
result = [name]
elif index_sum == best_sum:
result.append(name)
return result
Complexity:
- Time: O(n + m), for building the map and scanning the second list.
- Space: O(n), for the position map.
Common follow-ups
- Return only the minimum position sum as well: track and return
best_sumalongside the result. - Handle case-insensitive matching: normalize strings, such as with
casefold(), before storing and comparing. - Process a very large second list as a stream: scan it incrementally while maintaining the current best sum and matching strings.