{x}
blog image

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.

Solution Explanation:

This problem asks to find common strings between two lists and return those with the minimum sum of indices. The most efficient approach leverages a hash table (or dictionary in Python) for fast lookups.

Algorithm:

  1. Create a Hash Table: A hash table (d) is created from list2. The keys are the strings in list2, and the values are their respective indices. This allows for O(1) average-case lookup time.

  2. Iterate and Compare: The code iterates through list1. For each string s in list1:

    • It checks if s exists as a key in the hash table d. If it does, this means s is a common string.
    • The indices i (from list1) and j (retrieved from d) are summed.
    • Minimum Index Sum Tracking: A variable mi (minimum index sum) keeps track of the lowest sum encountered so far.
      • If i + j is less than mi, it means a new minimum sum is found. The ans (answer array) is reset to contain only s, and mi is updated.
      • If i + j equals mi, it means another string has the same minimum index sum; s is appended to ans.

  3. Return Result: Finally, the function returns the ans array containing all common strings with the minimum index sum.

Time Complexity Analysis:

  • Creating the hash table from list2 takes O(n2) time, where n2 is the length of list2.
  • Iterating through list1 takes O(n1) time, where n1 is the length of list1. The hash table lookup inside the loop is O(1) on average.
  • Therefore, the overall time complexity is dominated by the iteration and is O(n1 + n2), which is linear with respect to the input sizes.

Space Complexity Analysis:

  • The hash table d stores at most n2 entries (strings and their indices).
  • The ans array stores at most min(n1, n2) strings (the number of common strings).
  • Thus, the space complexity is O(n2) in the worst case (when all strings from list2 are unique and present in list1), or potentially lower if there are many duplicates.

The provided code in Python, Java, C++, Go, TypeScript, and Rust all implement this algorithm effectively, with minor syntactic differences depending on the language's features (e.g., use of HashMap vs. built-in dictionaries). The core logic remains consistent across all the implementations.