LeetCode 599: Minimum Index Sum of Two Lists

Problem Restatement

We are given two string arrays, list1 and list2.

A common string is a string that appears in both arrays.

For each common string, compute its index sum:

index in list1 + index in list2

We need to return all common strings with the smallest index sum. The answer may be returned in any order.

The problem guarantees that both lists have unique strings and that there is at least one common string. The list lengths are between 1 and 1000.

Input and Output

Example function shape:

def findRestaurant(list1: list[str], list2: list[str]) -> list[str]:
    ...

Examples

Example 1:

list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]
list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]

Output:

["Shogun"]

The only common string is "Shogun".

Example 2:

list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]
list2 = ["KFC", "Shogun", "Burger King"]

Output:

["Shogun"]

Common strings:

The smallest index sum is 1, so the answer is ["Shogun"].

Example 3:

list1 = ["happy", "sad", "good"]
list2 = ["sad", "happy", "good"]

Output:

["sad", "happy"]

Both "happy" and "sad" have index sum 1, so both are returned.

First Thought: Compare Every Pair

A direct solution is to compare every string in list1 with every string in list2.

If the strings match, compute the index sum.

This works, but it takes:

O(len(list1) * len(list2))

With lists up to length 1000, this is still possible, but we can do better with a hash map.

Key Insight

We need to quickly answer:

Where does this string appear in list1?

A hash map can store:

restaurant name -> index in list1

Then we scan list2.

For each string in list2, if it appears in the hash map, it is common to both lists. We compute:

index_map[name] + index_in_list2

Then we track the smallest sum seen so far.

Algorithm

1. Build a hash map from each string in list1 to its index.
2. Initialize:
   • best_sum = infinity
   • answer = []
3. Scan list2 with index j.
4. If list2[j] exists in the hash map:
   • Compute current_sum = index_map[list2[j]] + j.
   • If current_sum < best_sum, replace the answer with this string.
   • If current_sum == best_sum, append this string.
5. Return answer.

Correctness

The hash map stores the exact index of every string in list1.

When the algorithm scans list2, every common string is detected because it appears in the hash map. For each detected common string, the algorithm computes its exact index sum.

The variable best_sum always stores the smallest index sum among the common strings processed so far. When a smaller sum is found, the previous answer list is cleared because those strings no longer have the minimum sum. When an equal sum is found, the string is appended because it is also optimal.

After the scan finishes, every common string has been considered exactly once. Therefore, answer contains exactly all common strings with the minimum index sum.

Complexity

Let:

m = len(list1)
n = len(list2)

String hashing also depends on string length, but each string length is at most 30 in the constraints.

Implementation

class Solution:
    def findRestaurant(self, list1: list[str], list2: list[str]) -> list[str]:
        index = {}

        for i, name in enumerate(list1):
            index[name] = i

        best_sum = float("inf")
        answer = []

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

            current_sum = index[name] + j

            if current_sum < best_sum:
                best_sum = current_sum
                answer = [name]
            elif current_sum == best_sum:
                answer.append(name)

        return answer

Code Explanation

This builds the lookup table:

index = {}

for i, name in enumerate(list1):
    index[name] = i

Since strings in list1 are unique, each name maps to exactly one index.

The best sum starts as infinity:

best_sum = float("inf")

The result list stores all strings tied for the best sum:

answer = []

Then we scan list2:

for j, name in enumerate(list2):

If the name is not in list1, it cannot be part of the answer:

if name not in index:
    continue

For a common string, compute the index sum:

current_sum = index[name] + j

If this sum is smaller than every previous sum, replace the answer:

if current_sum < best_sum:
    best_sum = current_sum
    answer = [name]

If this sum ties the best known value, append it:

elif current_sum == best_sum:
    answer.append(name)

Finally:

return answer

returns all common strings with the smallest index sum.

Testing

def normalize(values):
    return sorted(values)

def run_tests():
    s = Solution()

    assert normalize(
        s.findRestaurant(
            ["Shogun", "Tapioca Express", "Burger King", "KFC"],
            ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"],
        )
    ) == normalize(["Shogun"])

    assert normalize(
        s.findRestaurant(
            ["Shogun", "Tapioca Express", "Burger King", "KFC"],
            ["KFC", "Shogun", "Burger King"],
        )
    ) == normalize(["Shogun"])

    assert normalize(
        s.findRestaurant(
            ["happy", "sad", "good"],
            ["sad", "happy", "good"],
        )
    ) == normalize(["sad", "happy"])

    assert normalize(
        s.findRestaurant(
            ["a", "b", "c"],
            ["c", "b", "a"],
        )
    ) == normalize(["b"])

    assert normalize(
        s.findRestaurant(
            ["a"],
            ["a"],
        )
    ) == normalize(["a"])

    print("all tests passed")

run_tests()

Test meaning: