Minimum Index Sum of Two Lists

Problem Statement

Two friends each give you a list of favourite restaurants, ordered by preference. Find the restaurants they have in common with the least index sum (index in list1 + index in list2).

If several restaurants tie for the least index sum, return all of them, in any order.

Input:  list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]
        list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
Output: ["Shogun"]
Why:    "Shogun" is the only common name — index 0 + index 3 = 3

Input:  list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]
        list2 = ["KFC", "Shogun", "Burger King"]
Output: ["Shogun"]
Why:    "Shogun"     → 0 + 1 = 1   ← smallest
        "Burger King" → 2 + 2 = 4
        "KFC"        → 3 + 0 = 3

Intuition

The naive method compares every name in list1 with every name in list2 — O(n × m) string comparisons, and string comparison itself is not free.

The second half is a standard "find the minimum, keeping ties" pattern:

• If the current index sum beats the best so far → throw away the old results and start a fresh list.
• If it equals the best → append to the results.
• If it is worse → ignore it.

Real-world analogy

Two people comparing restaurant shortlists. Rather than reading both lists aloud against each other, one person writes their list on a board with rank numbers. The other then reads their own list once, glancing at the board for each name.

Approach

Watch it run

Solution

def find_restaurant(list1: list[str], list2: list[str]) -> list[str]:
    """Common restaurants with the smallest index sum (all ties included)."""
    index_of = {name: i for i, name in enumerate(list1)}

    best = float("inf")
    results: list[str] = []

    for j, name in enumerate(list2):
        if name not in index_of:
            continue

        total = index_of[name] + j
        if total < best:
            best = total
            results = [name]      # strictly better — replace
        elif total == best:
            results.append(name)  # tie — keep both

    return results

An early-exit refinement

Once you are j steps into list2, no future match can have an index sum below j. So if best <= j, nothing further can improve it and you may stop:

for j, name in enumerate(list2):
    if j > best:
        break
    ...

This does not change the worst-case complexity but often ends the scan very early, since good matches tend to appear near the front.

Complexity Analysis

• Time — O(n) to build the map plus O(m) to scan list2, with O(1) average lookups. The brute force is O(n × m) string comparisons.
• Space — the map holds all n names from list1.

Edge Cases

Related Problems

• Two Sum — the same "turn a search into a lookup" move
• Group Anagrams — hash maps keyed by strings
• Unique Email Addresses — sets of normalised strings