LeetCode 599: Minimum Index Sum of Two Lists Solution in Python – A Step-by-Step Guide

What Is LeetCode 599: Minimum Index Sum of Two Lists?

In LeetCode 599: Minimum Index Sum of Two Lists, you’re given two string arrays list1 and list2, representing preferences (e.g., restaurant names), and your task is to return a list of all common strings with the minimum sum of their indices from both lists. If multiple strings share the same minimum index sum, return all of them. For example, with list1 = ["Shogun","Tapioca","Burger"] and list2 = ["Burger","Shogun"], the result is ["Shogun"] because "Shogun" has an index sum of 1 (0 from list1 + 1 from list2), the smallest among common elements. This problem builds on LeetCode 1: Two Sum for hash map usage but focuses on minimizing index sums for common elements.

Problem Statement

• Input:
• list1 (List[str])—first list of strings.
• list2 (List[str])—second list of strings.
• Output: List[str]—common strings with minimum index sum.
• Rules: Index sum = index in list1 + index in list2; return all with min sum; indices start at 0.

Constraints

• 1 <= list1.length, list2.length <= 1000
• 1 <= list1[i].length, list2[i].length <= 30
• Strings consist of spaces and English letters
• May contain duplicates

Examples

• Input: list1 = ["Shogun","Tapioca","Burger"], list2 = ["Burger","Shogun"]
• Output: ["Shogun"]
• "Shogun": 0+1=1, "Burger": 2+0=2, min sum = 1.
• Input: list1 = ["Shogun","Tapioca","Burger"], list2 = ["Tapioca","Shogun"]
• Output: ["Shogun","Tapioca"]
• "Shogun": 0+1=1, "Tapioca": 1+0=1, min sum = 1.
• Input: list1 = ["happy"], list2 = ["sad"]
• Output: []
• No common elements.

Understanding the Problem: Finding Common Favorites

To solve LeetCode 599: Minimum Index Sum of Two Lists in Python, we need to identify all common strings between two lists and find those with the smallest sum of their indices, handling up to 1000 elements per list efficiently. A brute-force approach checking every pair (O(n*m)) could work but is slow for large lists (n, m = list lengths). Instead, a hash map approach builds an index lookup for one list in O(n) time, then scans the other in O(m), tracking the minimum index sum and collecting matches, achieving O(n + m) efficiency. We’ll explore:

• Best Solution (Hash Map with Index Sum Tracking): O(n + m) time, O(n) space—fast and optimal.
• Alternative Solution (Brute-Force Nested Loops): O(n*m) time, O(1) space—thorough but slower.

Let’s dive into the hash map solution with a friendly breakdown!

Best Solution: Hash Map with Index Sum Tracking

Why Hash Map Wins

The hash map with index sum tracking solution is the best for LeetCode 599 because it finds common strings with the minimum index sum in O(n + m) time and O(n) space by mapping one list’s strings to their indices in a single pass, then scanning the second list to compute sums and track the minimum efficiently. It’s like making a quick lookup table of your friend’s favorite spots, then checking your list to see which matches come up first—all in a swift, organized tally!

How It Works

Think of this as a list-matching organizer:

• Step 1: Build Hash Map:
• Map each string in list1 to its index using a dictionary.
• Step 2: Scan Second List:
• For each string in list2:
• If in map, compute index sum (list1 index + list2 index).
• Track min sum and collect strings with that sum.
• Step 3: Return Result:
• List of strings with minimum index sum.
• Why It Works:
• Hash map provides O(1) lookups for list1 indices.
• Single pass per list ensures efficiency.

It’s like a min-sum matching maestro!

Step-by-Step Example

Example: list1 = ["Shogun","Tapioca","Burger"], list2 = ["Burger","Shogun"]

• Step 1: Build hash map:
• index_map = {"Shogun": 0, "Tapioca": 1, "Burger": 2}.
• Step 2: Scan list2:
• "Burger": In map, index = 2, sum = 2 + 0 = 2, min_sum = 2, result = ["Burger"].
• "Shogun": In map, index = 0, sum = 0 + 1 = 1, min_sum = 1, result = ["Shogun"].
• Step 3: Return ["Shogun"] (min sum = 1).
• Result: ["Shogun"].

Example: list1 = ["Shogun","Tapioca"], list2 = ["Tapioca","Shogun"]

• Step 1: index_map = {"Shogun": 0, "Tapioca": 1}.
• Step 2:
• "Tapioca": Sum = 1 + 0 = 1, min_sum = 1, result = ["Tapioca"].
• "Shogun": Sum = 0 + 1 = 1, min_sum = 1, result = ["Tapioca", "Shogun"].
• Step 3: Return ["Shogun", "Tapioca"] (min sum = 1).
• Result: ["Shogun", "Tapioca"].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

from typing import List

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        # Step 1: Build hash map of list1 with indices
        index_map = {s: i for i, s in enumerate(list1)}

        # Step 2: Track min sum and result list
        min_sum = float('inf')
        result = []

        # Step 3: Scan list2 and compute index sums
        for j, s in enumerate(list2):
            if s in index_map:
                curr_sum = index_map[s] + j
                if curr_sum < min_sum:
                    min_sum = curr_sum
                    result = [s]
                elif curr_sum == min_sum:
                    result.append(s)

        # Step 4: Return result
        return result

• Line 6: Create hash map of list1 strings to indices.
• Lines 9-10: Initialize min_sum as infinity, empty result list.
• Lines 13-19: Scan list2:
• If string in map, compute sum, update min_sum and result.
• Line 22: Return list of min-sum strings.
• Time Complexity: O(n + m)—one pass per list.
• Space Complexity: O(n)—hash map storage.

It’s like a list-matching wizard!

Alternative Solution: Brute-Force Nested Loops

Why an Alternative Approach?

The brute-force nested loops approach checks every pair of strings between the lists, computing index sums for common elements, running in O(n*m) time and O(1) space (excluding output). It’s thorough but inefficient for large lists, making it a good baseline for small inputs or understanding without hash maps.

How It Works

Picture this as a list-scanning seeker:

• Step 1: Initialize min sum and result list.
• Step 2: For each string in list1, scan list2 for matches.
• Step 3: Compute index sum, update min sum and result.
• Step 4: Return result list.

It’s like a manual match finder!

Step-by-Step Example

Example: list1 = ["Shogun","Tapioca"], list2 = ["Tapioca","Shogun"]

• Step 1: Min_sum = inf, result = [].
• Step 2: Scan:
• "Shogun": Match at list2[1], sum = 0 + 1 = 1, min_sum = 1, result = ["Shogun"].
• "Tapioca": Match at list2[0], sum = 1 + 0 = 1, min_sum = 1, result = ["Shogun", "Tapioca"].
• Step 3: Return ["Shogun", "Tapioca"].
• Result: ["Shogun", "Tapioca"].

Code for Brute-Force Approach

from typing import List

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        # Step 1: Initialize min sum and result
        min_sum = float('inf')
        result = []

        # Step 2: Check every pair
        for i in range(len(list1)):
            for j in range(len(list2)):
                if list1[i] == list2[j]:
                    curr_sum = i + j
                    if curr_sum < min_sum:
                        min_sum = curr_sum
                        result = [list1[i]]
                    elif curr_sum == min_sum:
                        result.append(list1[i])

        # Step 3: Return result
        return result

• Lines 6-7: Initialize min_sum and result.
• Lines 10-17: Nested loops to find matches, update min_sum and result.
• Line 20: Return result list.
• Time Complexity: O(n*m)—nested loops.
• Space Complexity: O(1)—minimal space (excluding output).

It’s a brute-force match seeker!

Comparing the Two Solutions

• Hash Map (Best):
• Pros: O(n + m), O(n), fast and elegant.
• Cons: Extra space for map.
• Brute-Force (Alternative):
• Pros: O(n*m), O(1), simple logic.
• Cons: Slower for large lists.

Hash map wins for efficiency!

Additional Examples and Edge Cases

• No common: [].
• Duplicates: Handled by first index.
• Single match: Single string result.

Hash map handles them all!

Complexity Recap

• Hash Map: Time O(n + m), Space O(n).
• Brute-Force: Time O(n*m), Space O(1).

Hash map’s the speed champ!

Key Takeaways

• Hash Map: Index finesse—learn at Python Basics!
• Brute-Force: Scan simplicity.
• Lists: Matching is fun.
• Python: Map or loops, your pick!

Final Thoughts: Match Those Lists!

LeetCode 599: Minimum Index Sum of Two Lists in Python is a fun matching challenge. Hash map with index sum tracking is your fast track, while brute-force offers a thorough dive. Want more? Try LeetCode 1: Two Sum or LeetCode 349: Intersection of Two Arrays. Ready to match? Head to Solve LeetCode 599 on LeetCode and find those common favorites today!