Minimum Index Sum of Two Lists

Given two string arrays list1 and list2, where every string appears at most once within the same list, return all common strings having the minimum index sum.

For a common string present at index i in list1 and index j in list2, the index sum equals i + j.

The answer may be returned in any order. Return an empty array when no common string exists.

Brute Force Approach

Every common string can be discovered by comparing each entry from list1 with each entry from list2. Without stored lookup information, complete pairwise comparison provides the most direct starting solution.

A running minimum avoids storing every common pair. A smaller index sum invalidates all previously collected answers, while an equal index sum represents another valid answer. Processing every pair guarantees that no common string remains unchecked.

Algorithm

• Initialize an empty list result to store common strings having the smallest index sum.

• Initialize minSum with infinity so that the first common string always becomes the initial answer.

• Traverse every index i in list1.

• Traverse every index j in list2 for each selected index i.

• Skip the current pair when list1[i] and list2[j] differ.

• Calculate currentSum = i + j after finding equal strings.

• Handle the calculated sum:

  • Clear result, update minSum, and insert the current string when currentSum < minSum.

  • Append the current string without clearing earlier answers when currentSum == minSum.

  • Ignore the current string when currentSum > minSum.

• Return result after processing every possible pair.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N × M × L), where N represents the number of strings in list1, M represents the number of strings in list2, and L represents the maximum string length. Every pair can require an O(L) string comparison.

Space Complexity: O(1) auxiliary space, excluding the returned strings. A result containing A strings requires O(A × L) output space.

Better Approach

Complete pairwise comparison repeatedly searches list1 for every string in list2. A Hash Map removes the repeated search by associating every string from list1 with the corresponding index.

A single traversal of list2 can then identify all common strings and calculate every index sum. This intermediate approach stores those matches inside a temporary list. Separate passes over the temporary list find the minimum sum and collect all tied strings.

Nested comparisons disappear, but the temporary match list and additional passes remain.

Algorithm

• Initialize a Hash Map indexInList1 to associate every string in list1 with the corresponding index.

• Traverse list1 and insert every string-index pair into indexInList1.

• Initialize an empty list commonMatches.

• Traverse list2 using index j.

• Search for list2[j] inside indexInList1.

• Store (j, indexInList1[list2[j]] + j) inside commonMatches when a matching string exists.

• Traverse commonMatches once to find the smallest stored index sum.

• Traverse commonMatches again and append every string whose stored sum equals the minimum.

• Return an empty result naturally when commonMatches contains no entries.

Dry Run

Solution

Complexity Analysis

Time Complexity: O((N + M) × L + C) on average, simplified to O((N + M) × L). N and M represent the list lengths, L represents the maximum string length, and C represents the number of common strings. Hashing and matching all input strings requires average O((N + M) × L) time, followed by two O(C) passes.

Space Complexity: O(N × L + C) auxiliary space. The Hash Map stores N string-index entries, while the temporary list stores one index-sum pair for every common string. A result containing A strings additionally requires O(A × L) output space.

Optimal Approach

The Better Approach stores every common match even though only matches having the smallest index sum are required. Most temporary entries are eventually discarded.

A running minimum can update the answer during the same traversal that discovers common strings. A smaller sum replaces the existing result, while an equal sum adds another answer. The temporary match list and both additional passes become unnecessary.

Indexing the smaller input list further reduces auxiliary storage. The sum of both indices remains unchanged after exchanging the roles of list1 and list2, because addition is commutative.

Algorithm

• Compare both list sizes.

• Select the smaller list as indexedList and the other list as scannedList, reducing the maximum number of Hash Map entries.

• Initialize a Hash Map indexMap.

• Traverse indexedList and associate every string with the corresponding index.

• Initialize minSum with infinity and result as an empty list.

• Traverse scannedList using index j.

• Skip the current string when no matching key exists inside indexMap.

• Calculate currentSum = indexMap[currentString] + j after finding a common string.

• Handle the calculated sum:

  • Clear result, update minSum, and insert the current string when currentSum < minSum.

  • Append the current string when currentSum == minSum.

  • Ignore the current string when currentSum > minSum.

• Return result after completing the traversal.

Dry Run

Solution

Complexity Analysis

Time Complexity: O((N + M) × L) on average, where N and M represent the two list lengths and L represents the maximum string length. Building the Hash Map and scanning the other list process every input string once.

Space Complexity: O(min(N, M) × L) auxiliary space when string-key contents are included. The Hash Map stores entries from only the smaller list. A result containing A strings additionally requires O(A × L) output space.

FAQs about Minimum Index Sum of Two Lists

1. Why is the result cleared after finding a smaller index sum?

Every previously stored string belongs to a larger index sum. Such strings can no longer remain inside the final answer after a smaller sum appears.

2. Why are equal index sums appended instead of replacing the result?

The required output contains all common strings sharing the minimum index sum. An equal sum represents another valid answer.

3. Why can the smaller list be stored inside the Hash Map?

Hash Map construction requires one entry per indexed string. Selecting the smaller list reduces the number of stored entries without changing the index-sum calculation.

4. Does exchanging the list roles change the index sum?

No. For indices i and j, both i + j and j + i produce the same value.

5. What happens when no common string exists?

No successful lookup occurs, so the result remains empty.

6. Why does the Optimal Approach not need a temporary common-match list?

Every discovered sum is compared directly with the running minimum. Smaller sums replace the result immediately, while equal sums are appended immediately.

7. Do Hash Map operations always require constant time?

Hash Map insertion and lookup require O(1) average operation count. String hashing and comparison can inspect up to L characters, where L represents the maximum string length. Severe hash collisions can also produce slower worst-case performance.

8. Can sorting solve the problem?

Yes. Original indices can be stored with every string, followed by sorting both collections and processing common strings with two pointers. The resulting time complexity includes sorting and remains slower than the average linear Hash Map solution.

9. Why is string uniqueness within each list important?

One stored index is sufficient only when every string occurs once per list. Repeated strings would require storing the earliest index or handling multiple indices explicitly.