Problem statement

Two friends each have a list of favourite restaurants. Find the common restaurants with the smallest index sum — the sum of a restaurant's position in list1 and its position in list2.

Return all such restaurants sorted in lexicographic order. There is always at least one common restaurant.

Example 1

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"]
Output: ["Shogun"]
Explanation: Shogun has index sum 0 + 1 = 1, the smallest.

Example 2

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Burger King","Tapioca Express","Shogun"]
Output: ["Burger King","KFC","Shogun","Tapioca Express"]
Explanation: Every restaurant has index sum 3, so all four tie and the answer is sorted.

Example 3

Input: list1 = ["happy","sad","good"], list2 = ["sad","happy","good"]
Output: ["happy","sad"]
Explanation: Both have index sum 1, and the answer is sorted.

Constraints

• 1 <= list1.length, list2.length <= 1000
• All strings within each list are distinct.
• There is at least one common string.

Hints for Minimum Index Sum of Two Lists

1. Hint 1

   Index list1 by name so you can look up positions in O(1).

2. Hint 2

   Sweep list2 and track the smallest index sum seen, resetting the answer when you beat it.

3. Hint 3

   Sort the collected names before returning — that is what makes the answer unique.

How to solve Minimum Index Sum of Two Lists

One hash lookup table plus one linear sweep. Ties are collected rather than replaced, then sorted to fix the output order.

Approach

1. Map each name in list1 to its index.
2. Walk list2. For a name present in the map, compute i + j.
3. If it beats the best sum, clear the answer and start it with this name; if it ties, append.
4. Sort the answer lexicographically and return it.

Why it works

Scanning list2 visits every common name exactly once, and tracking a running minimum with tie collection captures all optimal names in a single pass. Sorting makes the result deterministic.

Complexity

• Time — O(n + m log m)
• Space — O(n)

Pitfalls

• Replacing instead of appending on a tie loses one of the answers.
• Returning in encounter order rather than sorted order fails the exact judge.
• Comparing every pair is O(n·m) and unnecessary.

Reference solution

Python

from typing import List

def findRestaurant(list1: List[str], list2: List[str]) -> List[str]:
    pos = {}
    for i, name in enumerate(list1):
        if name not in pos:
            pos[name] = i
    best = None
    out = []
    for j, name in enumerate(list2):
        if name not in pos:
            continue
        s = pos[name] + j
        if best is None or s < best:
            best = s
            out = [name]
        elif s == best:
            out.append(name)
    out.sort()
    return out

Java

public static String[] findRestaurant(String[] list1, String[] list2) {
    HashMap<String, Integer> pos = new HashMap<>();
    for (int i = 0; i < list1.length; i++) {
        if (!pos.containsKey(list1[i])) pos.put(list1[i], i);
    }
    int best = Integer.MAX_VALUE;
    ArrayList<String> out = new ArrayList<>();
    for (int j = 0; j < list2.length; j++) {
        Integer i = pos.get(list2[j]);
        if (i == null) continue;
        int s = i + j;
        if (s < best) { best = s; out.clear(); out.add(list2[j]); }
        else if (s == best) out.add(list2[j]);
    }
    Collections.sort(out);
    return out.toArray(new String[0]);
}

C++

vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
    unordered_map<string, int> pos;
    for (int i = 0; i < (int) list1.size(); i++) {
        if (pos.find(list1[i]) == pos.end()) pos[list1[i]] = i;
    }
    int best = INT_MAX;
    vector<string> out;
    for (int j = 0; j < (int) list2.size(); j++) {
        auto it = pos.find(list2[j]);
        if (it == pos.end()) continue;
        int s = it->second + j;
        if (s < best) { best = s; out.clear(); out.push_back(list2[j]); }
        else if (s == best) out.push_back(list2[j]);
    }
    sort(out.begin(), out.end());
    return out;
}

JavaScript

var findRestaurant = function(list1, list2) {
    const pos = {};
    for (let i = 0; i < list1.length; i++) {
        if (pos[list1[i]] === undefined) pos[list1[i]] = i;
    }
    let best = Infinity;
    let out = [];
    for (let j = 0; j < list2.length; j++) {
        const i = pos[list2[j]];
        if (i === undefined) continue;
        const s = i + j;
        if (s < best) { best = s; out = [list2[j]]; }
        else if (s === best) out.push(list2[j]);
    }
    out.sort();
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy