599. Minimum Index Sum of Two Lists

Problem Description

The problem involves two lists of strings, list1 and list2. Our goal is to identify strings that appear in both lists (common strings) and among those, we want to find the ones that have the smallest index sum. The index sum for a common string is defined as the sum of its indexes in list1 and list2, i.e., if a string is at position i in list1 and at position j in list2, then its index sum is i + j. If there are multiple common strings with the same minimum index sum, we need to return all of them in any order.

This is a practical problem that could be applied to real-world scenarios where we are interested in finding common elements between two sets but prioritizing those that rank higher in both sets. For instance, in recommendation systems where the two lists represent preferences of two different users, and we want to find a common ground that considers the most preferred options by both.

Intuition

The solution is based on the idea of mapping one list into a dictionary (in this case, list2) to allow efficient lookups while iterating over the other list (list1). By maintaining this dictionary, we can check if an element from list1 appears in list2 in constant time rather than linear time, which would be the case if we were to scan list2 repeatedly.

As we want to find the least index sum, we start by assuming a high index sum (e.g., 2000) as the initial minimum mi. While iterating through list1, we check for common strings using the previously mentioned dictionary. When we find a common string, we calculate the index sum t and compare it to our current minimum index sum mi:

• If t is less than mi, it means we've found a new common string with a smaller index sum. We then update mi to this smaller value and start our answer list ans afresh with this string.
• If t is equal to the current minimum mi, it signifies that we've found another common string with the same lowest index sum. Therefore, we add this string to our ans list without resetting it.

This way, at the end of the iteration, the ans list contains all the common strings with the minimum index sum, and we return this list as the result.

Solution Approach

The solution provided is a practical combination of a hash map (referred to as a dictionary in Python) and a simple linear scan of the two lists. Here's a step-by-step breakdown of the implemented algorithm using the provided code:

1. Create a dictionary for efficient lookups: A dictionary mp is constructed to map the elements of list2 to their indexes. This allows for constant-time checks to see if an element from list1 also exists in list2, and if it does, we can instantly obtain its index in list2.

   1mp = {v: i for i, v in enumerate(list2)}

2. Initialize variables: A variable mi is initialized to a large number (2000 in this case, assuming that the sum of indexes will not exceed this number) to represent the smallest index sum we have found so far. An empty list ans is also initialized to store the answer strings.

3. Iterate through the first list (list1): We use a loop to go through each item v in list1 and its associated index i.

   1for i, v in enumerate(list1):
   2    ...

4. Check for common elements and calculate index sums: Within the loop, we check if element v is in the dictionary mp. If it is a common element, we calculate the total index sum t for that element.

   1if v in mp:
   2    t = i + mp[v]

5. Compare the index sum with the minimum: For each common element found, we compare the index sum t against the current minimum mi.

   • If t is smaller than mi, this means we've found a new common element with a smaller index sum. We update mi to the new smaller index sum and reset the ans array to only include this element.

     1if t < mi:
     2    mi = t
     3    ans = [v]

   • If t is equal to the current minimum (mi), this means we have found another common element with the same least index sum. We simply add this element to the ans array.

     1elif t == mi:
     2    ans.append(v)

6. Return the result: Once the loop is done, ans contains all the common elements with the least index sum. We return this list as the final answer.

The core algorithm can be seen as a "brute-force" approach improved with a hash map to avoid an unneeded second loop through list2. By only needing to iterate through each list once, the algorithm achieves a time complexity of O(n + m) where n is the length of list1 and m is the length of list2. If we used nested loops without a hash map, the time complexity would have been O(n * m), significantly slower for larger lists.

Example Walkthrough

Let's go through a small example to illustrate the solution approach. Assume our inputs are as follows:

1list1 = ["pineapple", "apple", "banana", "cherry"]
2list2 = ["berry", "apple", "cherry", "banana"]

Our goal is to find the common strings with the smallest index sum. Following our solution approach:

1. Create a dictionary for efficient lookups: We start by mapping list2 to a dictionary mp where each value is associated with its index.

   1mp = {"berry":0, "apple":1, "cherry":2, "banana":3}

2. Initialize variables: Set mi to a large number, let's say mi = 2000, and ans = [].

3. Iterate through list1:

   1for i, v in enumerate(list1):

   At this step, the loop will go through "pineapple", "apple", "banana", "cherry" at indices 0, 1, 2, 3 respectively.

4. Check for common elements and calculate index sums: When we reach "apple", which is at index 1 in list1, we find it in mp (it's at index 1 in list2 as well).

   1if v in mp:  # v is "apple"
   2    t = i + mp[v]  # t is 1 + 1 = 2

   Since "apple" is common, we calculate index sum t = 2.

5. Compare the index sum with the minimum: Since t (2) is less than mi (2000), we update mi to 2, and our answer list now contains "apple".

   1if t < mi:
   2    mi = t  # mi is now 2
   3    ans = [v]  # ans is now ["apple"]

   Continuing the iteration, we eventually come across "banana" at index 2 in list1 and at index 3 in list2. The index sum t is 5, which is greater than mi, so we don't update mi or ans.

   Next, for "cherry" at index 3 in list1 and index 2 in list2, the index sum t is 5 again, still greater than mi, so we still don't update mi or ans.

6. Return the result: At the end of the loop, ans contains ["apple"], which is the common element with the smallest index sum. This is our final answer.

And that is a direct application of the described algorithm, demonstrating with our small example that "apple" is common to both lists and has the smallest index sum of 2.

Solution Implementation

Time and Space Complexity

The time complexity of the given code is O(N + M), where N is the length of list1 and M is the length of list2. This is because the code iterates through list2 once to create a hash map of its elements along with their indices and then iterates through list1 to check if any element exists in list2 and perform index summation and comparison. Each of these operations (hash map lookups, summation, and comparison) are O(1), so the overall time complexity is determined by the lengths of the lists.

The space complexity of the code is O(M), where M is the length of list2. This is due to the creation of a hash map that might contain all elements of list2. The ans list has a space complexity of O(min(N, M)) in the worst case, where we must store a list of restaurants found in both list1 and list2. However, this does not change the overall space complexity, which is dominated by the size of the hash map.

Learn more about how to find time and space complexity quickly using problem constraints.