Minimum Index Sum of Two Lists: Finding Common Favorites Efficiently

May 20, 20264 min read

leetcodeproblemeasyarrayshash-mapstrings

Imagine you and a friend each have a ranked list of your favorite restaurants, and you want to figure out which ones you both like while prioritizing the ones ranked highest on both lists. That is exactly what LeetCode 599: Minimum Index Sum of Two Lists asks you to do. Given two arrays of strings, find the common strings that have the smallest combined index (the sum of their positions in both lists). If multiple strings share the same minimum index sum, return all of them.

Matching restaurants connected by index sum. "Shogun" has the smallest sum (0 + 1 = 1).

Why this problem matters

This problem is a clean example of using a hash map to bridge two data sources. The brute-force approach would check every pair of elements across the two lists, giving you O(m * n) time. But by indexing one list into a hash map first, you can look up each element from the second list in O(1), bringing the total down to O(m + n). That "index one, scan the other" pattern is everywhere - from database joins to Two Sum to Group Anagrams.

The approach

The strategy is simple:

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

This gives you the answer in a single pass through each list.

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

You can add an early termination optimization: if j alone already exceeds min_sum, no future match from this point can beat the current minimum (since index sums only grow as j increases). In practice this rarely matters for typical input sizes, but it is a nice detail to mention in an interview.

Practice this problem with spaced repetition

Step-by-step walkthrough

Let's trace through list1 = ["Shogun", "Tapioca", "Burger", "KFC"] and list2 = ["KFC", "Shogun", "Burger"].

Step 1: Build hash map from list1

Store each restaurant name and its index. This takes O(m) time and lets us do O(1) lookups.

Step 2: Scan list2, j=0 "KFC"

"KFC" is in the map at index 3. Index sum = 3 + 0 = 3. This is the first match, so set min_sum to 3.

Step 3: Scan list2, j=1 "Shogun"

"Shogun" is in the map at index 0. Index sum = 0 + 1 = 1. This beats the current min_sum of 3, so replace the result.

Step 4: Scan list2, j=2 "Burger King"

"Burger King" is in the map at index 2. Index sum = 2 + 2 = 4. This exceeds min_sum of 1, so skip it.

Step 5: Return result

All of list2 has been scanned. The minimum index sum is 1, achieved by "Shogun". Return ["Shogun"].

One pass to build the map, one pass to scan. The hash map turns what would be a nested search into a linear scan with constant-time lookups.

Complexity analysis

Metric	Value	Reasoning
Time	O(m + n)	Building the map from list1 takes O(m). Scanning list2 takes O(n). Each lookup is O(1) on average.
Space	O(m)	The hash map stores all m entries from list1. The result list is at most min(m, n) but does not dominate.

Build your pattern library with CodeBricks

Edge cases to watch for

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 have exactly one element and it matches, the answer is that element with index sum 0. If they do not match, return 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 just return all matches.
No shared elements. None of the strings overlap. The result is an empty list.

The building blocks

This problem is built on the same "index one, scan the other" hash map pattern you see in Two Sum. The core idea is identical: pre-process one collection into a dictionary so you can answer membership and lookup queries in O(1) while iterating through the second collection.

The difference is what you are optimizing. In Two Sum, you are looking for a specific complement. Here, you are tracking a running minimum across all matches. But the underlying technique - build a map, scan, and query - is the same brick.

Once you internalize this pattern, you will recognize it in problems like:

Finding common elements between collections
Matching items across two datasets
Any scenario where a nested loop can be flattened by pre-indexing one side

From understanding to recall

You have read through the solution and it makes sense. But will you be able to reproduce it in two weeks when an interviewer asks a variation? The hash map setup, the min_sum tracking, the tie-breaking logic with elif - these details slip away faster than you think.

Spaced repetition locks them in. CodeBricks breaks this problem into its building blocks and drills them at increasing intervals. You type the solution from understanding, not rote memory. After a few review cycles, the "index one, scan the other" pattern becomes automatic.

Two Sum - The classic hash map complement lookup problem that uses the same "build a map, scan the other" pattern
Group Anagrams - Another hash map grouping problem where you index strings by a computed key
Intersection of Two Linked Lists - Finding shared elements across two data structures, solved with a different technique

Try CodeBricks free