Minimum Index Sum of Two Lists

Easy

Yelp

2 views

Topics:

ArraysStrings

Given two arrays of strings list1 and list2, find the common strings with the least index sum.

A common string is a string that appeared in both list1 and list2.

A common string with the least index sum is a common string such that if it appeared at list1[i] and list2[j] then i + j should be the minimum value among all the other common strings.

Return all the common strings with the least index sum. Return the answer in any order.

Example 1:

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

Example 2:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"]
Output: ["Shogun"]
Explanation: 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"]
Explanation: 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.

Try coding it in LeetCode

Minimum Index Sum of Two Lists

Easy

Yelp

2 views

Topics:

ArraysStrings

Given two arrays of strings list1 and list2, find the common strings with the least index sum.

A common string is a string that appeared in both list1 and list2.

A common string with the least index sum is a common string such that if it appeared at list1[i] and list2[j] then i + j should be the minimum value among all the other common strings.

Return all the common strings with the least index sum. Return the answer in any order.

Example 1:

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

Example 2:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"]
Output: ["Shogun"]
Explanation: 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"]
Explanation: 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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input lists be empty, and if so, what should the return value be?
What is the expected range for the lengths of `list1` and `list2`?
If there are no common restaurants between `list1` and `list2`, what should I return?
Are the restaurant names guaranteed to be unique within each list?
If multiple restaurants share the same minimum index sum, is the order of the restaurants in the output important?

Brute Force Solution

Approach

The brute force way to solve this is to check every possible combination of words from the two lists. We are looking for common words and tracking which ones appear earliest in both lists. Then we pick the common word combination that has the lowest combined early position.

Here's how the algorithm would work step-by-step:

Go through each word in the first list one by one.
For each of those words, check every word in the second list to see if they match.
If you find a match, remember the positions where you found the matching words in both lists.
Calculate the sum of these positions.
Keep track of all the sums you calculated and the words that produced them.
Find the smallest sum among all the sums you calculated.
Finally, return the words that produced that smallest sum.

Code Implementation

def find_restaurant(list1, list2):
    minimum_index_sum = float('inf')
    result = []

    # Iterate through the first list
    for first_list_index in range(len(list1)):
        for second_list_index in range(len(list2)):

            # Check for common strings
            if list1[first_list_index] == list2[second_list_index]:

                current_index_sum = first_list_index + second_list_index

                # Compare index sum to minimum and update
                if current_index_sum < minimum_index_sum:
                    minimum_index_sum = current_index_sum
                    result = [list1[first_list_index]]

                # Accumulate matching restaurant names
                elif current_index_sum == minimum_index_sum:
                    result.append(list1[first_list_index])

    return result

Big(O) Analysis

Time Complexity

O(n²) – The described brute force algorithm iterates through each of the n words in the first list. For each of these words, it iterates through all m words in the second list to find a match. In the worst-case scenario, where n and m are of comparable size, let's denote them both as n, which means that for each word in the first list, we potentially compare it to every word in the second list. Therefore, the total number of comparisons approximates n * n operations, which simplifies to a time complexity of O(n²).

Space Complexity

O(N) – The brute force approach, as described, requires storing all calculated sums and the corresponding words that produced them. In the worst-case scenario, where a large number of words are common to both lists, we might store close to N such sums and word combinations, where N represents the length of the longer list. This is because in the worst case you have list1 = [a,b,c] list2 = [a,b,c], resulting in 3 stored values of sums and strings. Therefore, the space complexity is O(N).

Optimal Solution

Approach

The key to solving this problem efficiently is to remember the location of each word in the first list. Then, when we look at the second list, we can quickly find out if a word is also in the first list and where it was located. This avoids checking every pair of words.

Here's how the algorithm would work step-by-step:

First, make a note of each word in the first list and its position. Think of it like creating a directory where you can quickly look up a word and find its position in the list.
Next, go through the second list, one word at a time.
For each word in the second list, check if it exists in the directory we made from the first list. If it doesn't exist, skip to the next word in the second list.
If the word exists in both lists, add the two positions together (its position in the first list and its position in the second list).
Keep track of the smallest sum of positions we have seen so far. Also, remember the words that gave us this smallest sum.
If we find another pair of words with a smaller sum, replace the previous smallest sum and the words.
At the end, return the words that gave us the smallest sum of positions. If there are multiple sets of words that have the same minimal index sum, return all of them.

Code Implementation

def findRestaurant(list1, list2):    word_index_map = {}
    for index, word in enumerate(list1):
        word_index_map[word] = index

    minimum_index_sum = float('inf')
    result = []

    for index2, word in enumerate(list2):
        if word in word_index_map:
            #We found a common word. Now calculate the index sum
            index_sum = word_index_map[word] + index2

            if index_sum < minimum_index_sum:
                #New smallest sum, reset the result
                minimum_index_sum = index_sum
                result = [word]
            elif index_sum == minimum_index_sum:
                #Another word with the same smallest sum
                result.append(word)

    return result

Big(O) Analysis

Time Complexity

O(n + m) – Creating the hash map (or directory) of the first list, which has size n, takes O(n) time. Iterating through the second list, which has size m, takes O(m) time. Inside the second loop, the hash map lookup takes O(1) on average. Therefore, the total time complexity is O(n) + O(m * 1) which simplifies to O(n + m), where n is the length of the first list and m is the length of the second list.

Space Complexity

O(N) – The algorithm uses a hash map (or dictionary) to store each word from the first list and its index. In the worst case, all words in the first list are unique, requiring storage for N words and their indices, where N is the length of the first list. While other variables are used, such as the smallest sum and the list of common words, their space usage is constant relative to N. Therefore, the dominant space complexity is determined by the hash map, which scales linearly with the size of the first list.

Edge Cases

Case	How to Handle
Both lists are empty	Return an empty list since there are no common interests.
One list is empty, the other is not	Return an empty list since there are no common interests.
One or both lists contain null or empty strings	Treat null/empty strings as valid strings for comparison purposes or filter them out before processing.
Lists have no common interests	Return an empty list if no common interests are found after iterating through both lists.
Lists have a single common interest at the very beginning	Correctly identifies and returns the single common interest with index sum 0.
Lists have a single common interest at the very end	Iterate through the entire lists to find the common interest at the end, resulting in potentially a large index sum.
Lists have multiple common interests with the same minimum index sum	Collect all common interests with the minimum index sum and return them as a list.
Very large lists that may cause performance issues	Using a HashMap for one list allows for O(n+m) time complexity, which is more efficient than O(n*m).