Leetcode – Minimum Index Sum of Two Lists Solution in Python

Spread the love

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:

  1. Store the index positions of each restaurant in list1 in a hash map.
  2. Initialize min_index_sum to infinity and result to an empty list.
  3. 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:

  1. Similar to the previous approach, we create a hash map from list1.
  2. We use a list comprehension to create a list of tuples containing index sums and common restaurants.
  3. 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.

Leave a Reply