#599

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Minimum Index Sum of Two Lists

Find the common strings between two lists with the smallest index sum in this easy problem involving array scanning and hash table lookups.

array hash table string

Problem Statement

Given two arrays of strings, list1 and list2, your task is to identify all common strings between the two lists and find the ones with the minimum sum of indices. A common string is one that appears in both list1 and list2.

For each common string, if it appears at list1[i] and list2[j], then the sum i + j should be minimized. Return all common strings that share the smallest index sum. If there are multiple strings with the same minimum sum, return them all.

Examples

Example 1

Input: 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

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

Output: ["Shogun"]

The common string with the least index sum is "Shogun" with index sum = (0 + 1) = 1.

Example 3

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

Output: ["sad","happy"]

There are three common strings: "happy" with index sum = (0 + 1) = 1. "sad" with index sum = (1 + 0) = 1. "good" with index sum = (2 + 2) = 4. The strings with the least index sum are "sad" and "happy".

Constraints

1 <= list1.length, list2.length <= 1000
1 <= list1[i].length, list2[i].length <= 30
list1[i] and list2[i] consist of spaces ' ' and English letters.
All the strings of list1 are unique.
All the strings of list2 are unique.
There is at least a common string between list1 and list2.

Solution Approach

Array Scanning and Hash Lookup

To solve the problem efficiently, iterate through list1 and store the index of each string in a hash table. Then, for each string in list2, check if it exists in the hash table and compute the index sum. Track the minimum index sum and return the corresponding strings.

Track the Minimum Index Sum

While iterating through both lists, maintain a variable for the smallest index sum encountered. If a smaller sum is found, update the result list. If multiple strings have the same index sum, add them to the result.

Return All Common Strings with the Smallest Index Sum

If multiple common strings have the same minimum index sum, ensure that all of them are returned in the result list. This can be done by maintaining a list of candidates and updating it when a new minimum sum is found.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution is O(n + m), where n and m are the lengths of list1 and list2, respectively. The space complexity is O(n) due to the hash table storing the indices of list1's elements.

What Interviewers Usually Probe

Understanding hash table usage for index lookup.
Ability to handle edge cases where multiple strings have the same index sum.
Proficiency in optimizing solutions with linear complexity.

Common Pitfalls or Variants

Common pitfalls

Not considering the possibility of multiple strings having the same index sum.
Failure to handle large lists efficiently within time constraints.
Incorrectly updating the result list when a new minimum index sum is found.

Follow-up variants

Find the common strings with the smallest index sum in sorted order.
Extend the problem to handle case insensitivity when comparing strings.
Modify the problem to return the total minimum index sum, not just the strings.

FAQ

How can I solve the Minimum Index Sum of Two Lists problem optimally?

You can solve the problem optimally by scanning list1 and using a hash table to track the indices of its elements, followed by scanning list2 to compute the index sums.

What is the time complexity of the Minimum Index Sum of Two Lists problem?

The time complexity is O(n + m), where n and m are the lengths of list1 and list2, respectively.

Can there be multiple strings with the same index sum in this problem?

Yes, if multiple common strings have the same minimum index sum, all of them should be returned in the result.

How do I handle edge cases for multiple strings with the same index sum?

When encountering multiple strings with the same index sum, make sure to store all such strings and return them in the result.

What is the best approach for solving Minimum Index Sum of Two Lists in an interview?

The best approach is to use a hash table for fast lookups and ensure your solution handles edge cases like multiple strings with the same index sum while maintaining an optimal time complexity.

terminal

Solution

Solution 1: Hash Table

We use a hash table $\textit{d}$ to record the strings in $\textit{list2}$ and their indices, and a variable $\textit{mi}$ to record the minimum index sum.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        d = {s: i for i, s in enumerate(list2)}
        ans = []
        mi = inf
        for i, s in enumerate(list1):
            if s in d:
                j = d[s]
                if i + j < mi:
                    mi = i + j
                    ans = [s]
                elif i + j == mi:
                    ans.append(s)
        return ans

Continue Practicing

#609 find duplicate file in system #648 replace words #522 longest uncommon subsequence ii