Minimum Index Sum of Two Lists

EASY

Description

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.

Approaches

Checkout 2 different approaches to solve Minimum Index Sum of Two Lists. Click on different approaches to view the approach and algorithm in detail.

Using a Hash Map

A more efficient approach is to use a hash map to reduce the time complexity. We can store all the strings of one list and their corresponding indices in a hash map. Then, we iterate through the second list and for each string, we check if it's present in the map. This avoids the nested loop and allows us to find common strings in linear time.

Algorithm

Create a HashMap to store strings from one list and their indices.
To optimize space, choose the shorter list to build the map. Let's assume it's list1.
Iterate through list1 with index i and populate the map with (string, index) pairs: map.put(list1[i], i).
Initialize minSum to Integer.MAX_VALUE and an empty list result.
Iterate through list2 with index j.
For each string list2[j], check if it exists in the map.
If it exists, retrieve its index i from the map.

Calculate the index sum `currentSum = i + j`.

```
If `currentSum < minSum`:
```
```
  Update `minSum` to `currentSum`.
```
```
  Clear `result` and add `list2[j]`.
```
```
Else if `currentSum == minSum`:
```
```
  Add `list2[j]` to `result`.
```
Finally, return the result list as an array.

This method leverages a hash map to achieve a significant performance improvement. First, we iterate through one of the lists (preferably the shorter one to save space) and store each string and its index in a map. This allows for constant-time average lookups.

Next, we iterate through the second list. For each string, we check if it exists as a key in our map. If it does, we've found a common string. We can then retrieve its index from the first list (stored as the value in the map) and calculate the index sum. We then compare this sum with the minimum sum found so far (minSum) and update minSum and the result list as needed, just like in the brute-force approach. This process reduces the search for a common string from a linear scan to a near-constant time operation.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        // Optimization: build map from the shorter list to save space.
        if (list1.length > list2.length) {
            return findRestaurant(list2, list1);
        }

        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < list1.length; i++) {
            map.put(list1[i], i);
        }

        List<String> result = new ArrayList<>();
        int minSum = Integer.MAX_VALUE;

        for (int j = 0; j < list2.length; j++) {
            Integer i = map.get(list2[j]);
            if (i != null) {
                int currentSum = i + j;
                if (currentSum < minSum) {
                    minSum = currentSum;
                    result.clear();
                    result.add(list2[j]);
                } else if (currentSum == minSum) {
                    result.add(list2[j]);
                }
            }
        }
        return result.toArray(new String[0]);
    }
}

Complexity Analysis

Time Complexity: O((L1 + L2) * S), where L1 and L2 are the lengths of the lists and S is the average string length. Populating the map takes O(L1*S) and iterating through the second list takes O(L2*S).Space Complexity: O(L_short * S), where L_short is the length of the shorter list and S is the average string length. This space is used for the hash map.

Pros and Cons

Pros:

Significantly more efficient with a linear time complexity.
The optimal solution for this problem in terms of time.

Cons:

Requires extra space for the hash map, which can be proportional to the size of one of the lists.

Code Solutions

Checking out 3 solutions in different languages for Minimum Index Sum of Two Lists. Click on different languages to view the code.

class Solution {
public
  String[] findRestaurant(String[] list1, String[] list2) {
    Map<String, Integer> mp = new HashMap<>();
    for (int i = 0; i < list2.length; ++i) {
      mp.put(list2[i], i);
    }
    List<String> ans = new ArrayList<>();
    int mi = 2000;
    for (int i = 0; i < list1.length; ++i) {
      if (mp.containsKey(list1[i])) {
        int t = i + mp.get(list1[i]);
        if (t < mi) {
          ans = new ArrayList<>();
          ans.add(list1[i]);
          mi = t;
        } else if (t == mi) {
          ans.add(list1[i]);
        }
      }
    }
    return ans.toArray(new String[0]);
  }
}

Video Solution

Watch the video walkthrough for Minimum Index Sum of Two Lists

Data Structures:

ArrayHash TableString

Companies:

Yelp |