Minimum Index Sum of Two Lists - Video Solutions

Problem Overview: You get two string arrays representing favorite restaurants from two people. The task is to return the restaurant(s) that appear in both lists with the smallest possible index sum i + j. If multiple restaurants share the same minimum sum, return all of them.

Approach 1: Hash Map Approach (O(n + m) time, O(n) space)

This is the standard solution using a hash table. First iterate through list1 and store each restaurant with its index in a hash map. Then iterate through list2. For every restaurant, check if it exists in the map using an O(1) lookup. If it exists, compute the index sum i + j. Track the smallest sum seen so far and update the result list accordingly. If a new smaller sum appears, clear the result and add the new restaurant; if the sum ties with the minimum, append it.

The key insight is constant‑time membership checking. Instead of comparing every pair of restaurants, you reduce the search to direct hash lookups. This turns a potential O(n*m) comparison into a linear scan. The approach works well for typical array intersection problems where fast membership checks are required.

Approach 2: Two Pointer / Incremental Index Scan (O(n^2) worst case, O(1) extra space)

This approach avoids extra data structures and instead scans both lists using increasing index sums. Start with sum = 0 and check all index pairs where i + j = sum. For each pair, compare the restaurant names directly. As soon as you find matches, record them. Once matches appear for a particular sum, you can stop because any later sums will be larger.

The technique behaves like a diagonal traversal over the conceptual matrix of index pairs. It is simple and uses constant extra space, relying only on string comparisons between the two lists. However, because comparisons may still grow quadratically in the worst case, it is less efficient for large inputs. Still, for short lists or environments where extra memory is restricted, it can be acceptable.

Since restaurant names are strings, equality checks are direct string comparisons. The main optimization comes from minimizing unnecessary comparisons or lookups.

Recommended for interviews: The hash map approach is what interviewers expect. It demonstrates recognition of a classic pattern: store indices in a map, then perform constant‑time lookups while scanning the second list. A brute force or incremental scan shows baseline reasoning, but the hash table solution proves you can reduce time complexity from quadratic to linear.