Minimum Index Sum of Two Lists: Hash Map Index Tracking

LeetCode 599, Minimum Index Sum of Two Lists, gives you two arrays of strings (think of them as ranked lists of favorite restaurants). You need to find the common strings that have the smallest combined index. If "Shogun" appears at index 0 in list1 and index 1 in list2, its index sum is 1. If multiple strings share the same minimum index sum, return all of them.

The brute-force approach checks every element of list1 against every element of list2, giving you O(m * n) time. But you can do much better. By storing one list in a hash map, you can look up each element from the other list in O(1) and compute index sums in a single pass.

The approach: hash map with index sums

The plan has three parts:

1. Build a hash map from list1, mapping each string to its index.
2. Walk through list2. For each string that exists in the map, compute the index sum (position in list1 plus position in list2).
3. Track the minimum index sum seen so far. If you find a smaller sum, replace the result list. If you find an equal sum, append to the result list.

This is the same "index one, scan the other" pattern that powers Two Sum. The difference is what you are optimizing. Two Sum looks for a specific complement. Here, you are tracking a running minimum across all matches.

The code

def findRestaurant(list1, list2):
    index_map = {val: i for i, val in enumerate(list1)}
    min_sum = float('inf')
    result = []

    for j, val in enumerate(list2):
        if val in index_map:
            idx_sum = index_map[val] + j
            if idx_sum < min_sum:
                min_sum = idx_sum
                result = [val]
            elif idx_sum == min_sum:
                result.append(val)

    return result

Walk through what happens:

1. index_map = {val: i for i, val in enumerate(list1)} builds a dictionary that maps every restaurant name to its index in list1. This takes one pass and O(m) space.
2. min_sum = float('inf') initializes the minimum to infinity so that any real index sum will beat it.
3. The for j, val in enumerate(list2) loop scans list2 once, checking each element against the map.
4. if val in index_map is the O(1) hash map lookup. If the restaurant is not in list1, you skip it entirely.
5. idx_sum = index_map[val] + j computes the combined index. You already have the list1 index from the map, and j is the list2 index.
6. If idx_sum is strictly less than min_sum, you found a new winner. Reset result to contain just this element.
7. If idx_sum equals min_sum, this element ties with the current winners. Append it to result.
8. After the loop finishes, return the result list.

Visual walkthrough

Here is a step-by-step trace showing how the hash map is built from list1, then how each element of list2 is looked up and scored. Watch how min_sum updates when a better match is found.

Notice that the entire algorithm uses two linear passes: one to build the map, one to scan. The hash map converts what would be nested O(m * n) searching into flat O(m + n) work.

Complexity analysis

Building the hash map from list1 takes O(m). Scanning list2 takes O(n), with each hash map lookup costing O(1) on average. The result list is at most min(m, n) entries, which does not dominate the space.

Building blocks

Index-one-scan-the-other

The core technique here is pre-processing one collection into a hash map so you can answer membership and lookup queries in constant time while iterating through the second collection. This is the same pattern behind Two Sum, where you store seen values in a dictionary and check for complements on each new element. Once you internalize this brick, you will recognize it in any problem where a nested loop can be flattened by pre-indexing one side.

Other problems that use this pattern:

• Two Sum (LeetCode 1) stores values in a map and checks for complements in a single pass.
• Intersection of Two Arrays II (LeetCode 350) builds a frequency map from one array and decrements counts while scanning the other.

Running minimum tracking

The second technique is maintaining a running minimum (or maximum) while scanning a sequence, and collecting all items that tie at the best value. The three-way branch (less than, equal to, greater than) is the standard template for this. You replace the result on a strict improvement and append on a tie.

Other problems that use this pattern:

• Two Sum II (LeetCode 167) tracks a target while scanning with two pointers.
• Group Anagrams (LeetCode 49) collects items by key, a related grouping technique.

Edge cases

Equal index sums. Multiple restaurants can tie for the minimum. For example, if list1 = ["A", "B"] and list2 = ["B", "A"], both "A" and "B" have index sum 1. You need to return both.

Single-element lists. If both lists contain exactly one element and it matches, the answer is that element with index sum 0. If they do not match, the result is an empty list.

All elements shared. Every element in list2 appears in list1. You still need to track which ones have the minimum index sum, not return all matches.

No shared elements. None of the strings overlap between the two lists. The result is an empty list because no match is ever found.

From understanding to recall

You can read through this solution and follow the logic. But the details that slip away over time are the specific ones: initializing min_sum to infinity, the three-way comparison with the elif branch for ties, and remembering to replace the entire result list (not just append) when a new minimum is found. These are exactly the kind of small decisions that trip you up under interview pressure.

Spaced repetition locks them in. You drill the "index one, scan the other" pattern as one brick and the running-minimum tracking as another. Each rep takes a minute or two. After a few rounds at increasing intervals, the dictionary comprehension and the three-way branch are automatic. When you see a problem that asks you to match across two collections, you are not rebuilding the logic from scratch. You are snapping together bricks you already own.

Related posts

• Two Sum - The classic hash map complement lookup that uses the same "build a map, scan the other" technique
• Group Anagrams - Another hash map problem where you index strings by a computed key and collect grouped results
• Contains Duplicate - The simplest hash set membership problem, a good warm-up before index tracking variations