599. Minimum Index Sum of Two Lists LeetCode Solution

In this guide, you will get 599. Minimum Index Sum of Two Lists LeetCode Solution with the best time and space complexity. The solution to Minimum Index Sum of Two Lists problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Index Sum of Two Lists solution in C++
Minimum Index Sum of Two Lists solution in Java
Minimum Index Sum of Two Lists solution in Python
Additional Resources

599. Minimum Index Sum of Two Lists LeetCode Solution image

Problem Statement of Minimum Index Sum of Two Lists

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.

Complexity Analysis

Time Complexity: O(m + n), where m = |\texttt{list1}| \cdot \max(|\texttt{list1[i]}|) and n = |\texttt{list2}| \cdot \max(|\texttt{list2[i]}|)
Space Complexity: O(n)

599. Minimum Index Sum of Two Lists LeetCode Solution in C++

class Solution {
 public:
  vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
    vector<string> ans;
    unordered_map<string, int> restaurantToIndex;
    int minSum = INT_MAX;

    for (int i = 0; i < list1.size(); ++i)
      restaurantToIndex[list1[i]] = i;

    for (int i = 0; i < list2.size(); ++i) {
      const string& restaurant = list2[i];
      if (const auto it = restaurantToIndex.find(restaurant);
          it != restaurantToIndex.cend()) {
        const int sum = it->second + i;
        if (sum < minSum) {
          minSum = sum;
          ans = {restaurant};
        } else if (sum == minSum) {
          ans.push_back(restaurant);
        }
      }
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

599. Minimum Index Sum of Two Lists LeetCode Solution in Java

class Solution {
  public String[] findRestaurant(String[] list1, String[] list2) {
    List<String> ans = new LinkedList<>();
    Map<String, Integer> restaurantToIndex = new HashMap<>();
    int minSum = Integer.MAX_VALUE;

    for (int i = 0; i < list1.length; ++i)
      restaurantToIndex.put(list1[i], i);

    for (int i = 0; i < list2.length; ++i) {
      final String restaurant = list2[i];
      if (restaurantToIndex.containsKey(restaurant)) {
        final int sum = restaurantToIndex.get(restaurant) + i;
        if (sum < minSum) {
          minSum = sum;
          ans.clear();
          ans.add(restaurant);
        } else if (sum == minSum) {
          ans.add(restaurant);
        }
      }
    }

    return ans.toArray(new String[0]);
  }
}
// code provided by PROGIEZ

599. Minimum Index Sum of Two Lists LeetCode Solution in Python

class Solution:
  def findRestaurant(self, list1: list[str], list2: list[str]) -> list[str]:
    ans = []
    restaurantToIndex = {restaurant: i for i,
                         restaurant in enumerate(list1)}
    minSum = math.inf

    for i, restaurant in enumerate(list2):
      if restaurant in restaurantToIndex:
        summ = restaurantToIndex[restaurant] + i
        if summ < minSum:
          ans.clear()
        if summ <= minSum:
          ans.append(restaurant)
          minSum = summ

    return ans
 # code by PROGIEZ