LeetCode 599 - Minimum Index Sum of Two Lists

Difficulty: 🟢 Easy
Topics: Array, Hash Table, String

Solution

Problem Understanding

This problem is asking us to find the common elements between two lists of strings, but not just any common elements. We want the ones where the sum of their indices in both lists is the smallest. In other words, if a string appears at index i in list1 and index j in list2, we calculate i + j. Among all common strings, we need the string(s) with the smallest i + j sum.

The input consists of two arrays of strings, list1 and list2, where each string is unique within its own list. The output should be a list of strings containing all common strings that have the minimum index sum. The constraints are relatively small (1 <= length <= 1000), so we can aim for an efficient solution using hashing.

Important edge cases include: lists with multiple common strings having the same minimum index sum, lists where all strings are common, or lists where the common string appears at the last index in both lists. The problem guarantees there is at least one common string, so we do not need to handle empty outputs.

Approaches

Brute Force

The naive brute-force approach is to compare every element in list1 with every element in list2, calculate their index sum if they match, and keep track of the smallest sum. While correct, this approach requires O(n * m) comparisons, where n and m are the lengths of list1 and list2. Given the constraints, this could be up to 1,000,000 comparisons, which is inefficient.

Optimal Approach

The key insight for a better solution is to use a hash map to store the indices of one list. By storing list1 in a map with its string as the key and its index as the value, we can then iterate over list2, check if the current string exists in the map, and calculate the index sum. We maintain a variable to track the minimum sum and a list to collect all strings that meet that sum. This reduces the time complexity to O(n + m) and makes the solution efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(1)	Compare all pairs of strings between both lists
Optimal	O(n + m)	O(n)	Use a hash map for fast lookup and track minimum index sum

Algorithm Walkthrough

Create an empty hash map to store the indices of strings in list1.
Iterate over list1 with index i and store each string and its index in the hash map.
Initialize min_sum to infinity and an empty list result to store the common strings with the least index sum.
Iterate over list2 with index j.
For each string in list2, check if it exists in the hash map.
If it exists, calculate the index sum i + j.
If the index sum is less than min_sum, update min_sum and reset result with this string.
If the index sum equals min_sum, append this string to result.
After processing all strings, return result.

Why it works: The hash map allows constant-time lookups for strings from list1. By tracking the minimum index sum and updating the result list accordingly, we guarantee that only strings with the least index sum are returned. The algorithm handles multiple strings with the same minimum sum naturally.

Python Solution

from typing import List

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        index_map = {restaurant: i for i, restaurant in enumerate(list1)}
        min_sum = float('inf')
        result = []

        for j, restaurant in enumerate(list2):
            if restaurant in index_map:
                total_index = index_map[restaurant] + j
                if total_index < min_sum:
                    min_sum = total_index
                    result = [restaurant]
                elif total_index == min_sum:
                    result.append(restaurant)
        
        return result

This Python implementation uses a dictionary comprehension to map strings to indices. We then iterate through list2, compute the index sum for common strings, and update the result list only when we find a smaller or equal index sum.

Go Solution

func findRestaurant(list1 []string, list2 []string) []string {
    indexMap := make(map[string]int)
    for i, restaurant := range list1 {
        indexMap[restaurant] = i
    }

    result := []string{}
    minSum := 1<<31 - 1 // max int value

    for j, restaurant := range list2 {
        if i, exists := indexMap[restaurant]; exists {
            total := i + j
            if total < minSum {
                minSum = total
                result = []string{restaurant}
            } else if total == minSum {
                result = append(result, restaurant)
            }
        }
    }
    return result
}

In Go, we use a map for index lookup and an integer minSum initialized to the maximum possible integer. We append or reset the result slice based on the current index sum, similar to the Python implementation. Go requires careful handling of slices and integer initialization, which differs from Python's flexibility with float('inf').

Worked Examples

Example 1

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

list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]

list2 index j	restaurant	index_map lookup	total_index	min_sum	result
0	Piatti	not in map	-	inf	[]
1	The Grill...	not in map	-	inf	[]
2	Hungry Hunter	not in map	-	inf	[]
3	Shogun	0	3+0=3	3	["Shogun"]

Output: ["Shogun"]

Example 2

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

list2 = ["KFC","Shogun","Burger King"]

list2 index j	restaurant	index_map lookup	total_index	min_sum	result
0	KFC	3	3+0=3	3	["KFC"]
1	Shogun	0	0+1=1	1	["Shogun"]
2	Burger King	2	2+2=4	1	["Shogun"]

Output: ["Shogun"]

Example 3

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

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

list2 index j	restaurant	index_map lookup	total_index	min_sum	result
0	sad	1	1+0=1	1	["sad"]
1	happy	0	0+1=1	1	["sad","happy"]
2	good	2	2+2=4	1	["sad","happy"]

Output: ["sad","happy"]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Constructing the map is O(n) and iterating list2 is O(m)
Space	O(n)	Hash map stores indices of list1

We achieve linear time and space by leveraging the hash map for fast lookups and tracking minimum index sums.

Test Cases

# Provided examples
assert Solution().findRestaurant(["Shogun","Tapioca Express","Burger King","KFC"], ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]) == ["Shogun"]  # single common
assert Solution().findRestaurant(["Shogun","Tapioca Express","Burger King","KFC"], ["KFC","Shogun","Burger King"]) == ["Shogun"]  # minimum index sum
assert set(Solution().findRestaurant(["happy","sad","good"], ["sad","happy","good"])) == {"sad","happy"}  # multiple with same index sum

# Edge cases
assert Solution().findRestaurant(["a"], ["a"]) == ["a"]  # smallest lists
assert Solution().findRestaurant(["a","b","c"], ["c","b","a"]) == ["b"]  # middle index sum minimum
assert set(Solution().findRestaurant(["x","y","z"], ["y","x","z"])) == {"x","y"}  # multiple minimum sums

Test	Why
Single common	Validates basic matching
Minimum index sum	Checks correct minimum selection
Multiple same sum	Ensures multiple strings with same sum are returned
Smallest lists	Edge case with minimal input
Middle index	Verifies algorithm selects correct index sum, not first element
Multiple minimum sums	Ensures