Among the abundant problems involving arrays and lists, the Minimum Index Sum of Two Lists problem (#599) on Leetcode holds a unique place due to its practicality and the variety of concepts it encompasses. In this article, we will meticulously unravel the problem, explore various approaches, and learn how to implement an efficient solution in Python.

## Problem Statement

The problem statement for Minimum Index Sum of Two Lists is as follows:

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.

You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.

Example:

```
Input: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"], list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
Output: ["Shogun"]
Explanation: The only restaurant they both like is "Shogun".
```

## Approaches to Solve the Problem

### 1. Using Hash Maps

A very intuitive and efficient approach to solving this problem involves the use of hash maps. We can store the index positions of each restaurant in the first list in a hash map. Then, as we iterate through the second list, we can check if a restaurant is common to both lists, and if so, calculate the index sum and update our answer accordingly.

```
def findRestaurant(list1, list2):
# Store the index of each restaurant in list1 in a hash map
index_map = {restaurant: index for index, restaurant in enumerate(list1)}
# Initialize minimum index sum and result list
min_index_sum = float("inf")
result = []
# Iterate through list2 and find common restaurants with minimum index sum
for index, restaurant in enumerate(list2):
if restaurant in index_map:
total_index = index + index_map[restaurant]
if total_index < min_index_sum:
min_index_sum = total_index
result = [restaurant]
elif total_index == min_index_sum:
result.append(restaurant)
return result
```

#### Explanation:

- Store the index positions of each restaurant in
`list1`

in a hash map. - Initialize
`min_index_sum`

to infinity and`result`

to an empty list. - Iterate through
`list2`

and for each restaurant, check if it exists in`list1`

by looking it up in the hash map. Calculate the index sum and update`min_index_sum`

and`result`

.

#### Time Complexity:

This approach has a time complexity of O(n + m), where n and m are the lengths of the two lists. The space complexity is O(n) due to the hash map.

### 2. Simplified Approach Using Python’s Built-in Functions

Python’s robust standard library can help us simplify and streamline the above approach.

```
def findRestaurant(list1, list2):
# Create a hash map from list1
index_map = {restaurant: index for index, restaurant in enumerate(list1)}
# Find common restaurants with minimum index sum
common = [(index + index_map[restaurant], restaurant) for index, restaurant in enumerate(list2) if restaurant in index_map]
# Sort by index sum and find restaurants with the minimum index sum
min_index_sum = min(common)[0]
return [restaurant for index_sum, restaurant in common if index_sum == min_index_sum]
```

#### Explanation:

- Similar to the previous approach, we create a hash map from
`list1`

. - We use a list comprehension to create a list of tuples containing index sums and common restaurants.
- We sort the list based on index sums and filter out the restaurants with the minimum index sum.

#### Time Complexity:

This approach has a similar time complexity of O(n + m) and space complexity of O(n).

## Conclusion

The Minimum Index Sum of Two Lists problem is a quintessential example of using hash maps for efficient lookup and list operations. It also illustrates how an understanding of Pythonâ€™s built-in functions can lead to more concise and readable code.