LeetCode 3682 - Minimum Index Sum of Common Elements

LeetCode Problem 3682

Difficulty: 🟡 Medium
Topics: Array, Hash Table

Solution

Problem Understanding

This problem is asking us to identify the smallest sum of indices from two equal-length arrays, nums1 and nums2, such that the elements at those indices are equal. Formally, we want a pair (i, j) where nums1[i] == nums2[j], and we want the minimum value of i + j. If no such pair exists, we return -1.

The inputs nums1 and nums2 are both integer arrays of length up to 105, and the integers themselves can range from -105 to 105. The output is a single integer representing the minimum index sum, or -1 if there are no common elements.

Important considerations include handling negative numbers, duplicates, and situations where multiple pairs share the same minimum sum. The arrays may also have no common elements at all, which must return -1. Edge cases to consider are arrays with all unique elements, arrays where every element is identical, and arrays of length 1.

Approaches

The brute-force approach is straightforward: iterate through every element in nums1 and, for each, iterate through every element in nums2 to check if they are equal. If a pair is found, calculate the index sum i + j and track the minimum. This is correct but inefficient because it requires O(n²) comparisons, which is too slow for n up to 105.

The optimal approach uses a hash map. We first map each element in nums1 to its index. Then we iterate through nums2 and check if the current element exists in the map. If it does, we compute the index sum and update the minimum if it is smaller than the current minimum. This reduces the time complexity to O(n) because hash map lookups are O(1) on average.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Nested iteration over both arrays to find matching elements
Optimal	O(n)	O(n)	Uses a hash map to store indices of nums1 and checks nums2 elements

Algorithm Walkthrough

1. Initialize an empty hash map index_map to store the value-to-index mapping of nums1.
2. Iterate through nums1 and populate index_map so that each key is an element of nums1 and the value is its index.
3. Initialize a variable min_sum to infinity to track the minimum index sum.
4. Iterate through nums2 with index j. For each element, check if it exists in index_map.
5. If it exists, calculate the index sum as i + j where i is the index from index_map. Update min_sum if this sum is smaller.
6. After completing the iteration, if min_sum is still infinity, return -1; otherwise, return min_sum.

Why it works: By mapping nums1 elements to indices, we guarantee that each lookup for a common element in nums2 is efficient. Tracking the minimum ensures we find the smallest index sum, and the algorithm correctly handles multiple common elements and duplicates.

Python Solution

from typing import List

class Solution:
    def minimumSum(self, nums1: List[int], nums2: List[int]) -> int:
        index_map = {num: i for i, num in enumerate(nums1)}
        min_sum = float('inf')
        
        for j, num in enumerate(nums2):
            if num in index_map:
                min_sum = min(min_sum, index_map[num] + j)
        
        return min_sum if min_sum != float('inf') else -1

The Python implementation first constructs a dictionary mapping elements of nums1 to their indices. It then iterates through nums2, checking for each element if it exists in the dictionary. If it does, the sum of indices is calculated and min_sum is updated. Finally, the code returns -1 if no common element was found or the minimum index sum otherwise.

Go Solution

func minimumSum(nums1 []int, nums2 []int) int {
    indexMap := make(map[int]int)
    for i, num := range nums1 {
        indexMap[num] = i
    }

    minSum := int(^uint(0) >> 1) // Max int
    found := false

    for j, num := range nums2 {
        if i, ok := indexMap[num]; ok {
            sum := i + j
            if sum < minSum {
                minSum = sum
            }
            found = true
        }
    }

    if !found {
        return -1
    }
    return minSum
}

In Go, the hash map indexMap is built using a standard map. The maximum integer is set using bit manipulation. The algorithm iterates through nums2, and the existence check uses the comma-ok idiom. A found flag tracks whether any common element was detected.

Worked Examples

Example 1:

nums1 = [3,2,1], nums2 = [1,3,1]

Iteration	nums2[j]	Exists in nums1?	Index Sum	min_sum
j=0	1	Yes (i=2)	2	2
j=1	3	Yes (i=0)	1	1
j=2	1	Yes (i=2)	4	1

Output: 1

Example 2:

nums1 = [5,1,2], nums2 = [2,1,3]

Iteration	nums2[j]	Exists in nums1?	Index Sum	min_sum
j=0	2	Yes (i=2)	2	2
j=1	1	Yes (i=1)	2	2
j=2	3	No	-	2

Output: 2

Example 3:

nums1 = [6,4], nums2 = [7,8]

No common elements exist, so output is -1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Building the map is O(n) and iterating through nums2 is O(n), giving total O(n)
Space	O(n)	Storing the index map requires O(n) space for nums1

The complexity is linear because each element is processed once, and hash map lookups are O(1).

Test Cases

# Provided examples
assert Solution().minimumSum([3,2,1], [1,3,1]) == 1  # Example 1
assert Solution().minimumSum([5,1,2], [2,1,3]) == 2  # Example 2
assert Solution().minimumSum([6,4], [7,8]) == -1     # Example 3

# Edge cases
assert Solution().minimumSum([1], [1]) == 0         # Single-element match
assert Solution().minimumSum([1], [2]) == -1        # Single-element no match
assert Solution().minimumSum([1,1,1], [1,1,1]) == 0 # Duplicates, minimal index sum is first
assert Solution().minimumSum([-1, -2, 3], [3, -1]) == 1 # Negative numbers

Test	Why
[3,2,1], [1,3,1]	Validates basic functionality and multiple matches
[5,1,2], [2,1,3]	Ensures minimum index sum is chosen correctly
[6,4], [7,8]	Checks for no common elements
[1], [1]	Single-element minimal case
[1], [2]	Single-element no match
[1,1,1], [1,1,1]	Multiple duplicates handled correctly
[-1,-2,3],[3,-1]	Handles negative numbers

Edge Cases

First, arrays of length 1 can be tricky because index sums are either 0 or non-existent; the implementation correctly handles this by returning either 0 or -1.

Second, arrays with negative numbers must be handled correctly in the hash map; since keys can be negative, Python and Go maps handle them natively, and the algorithm works without modification.

Third, duplicates in either array could lead to multiple valid pairs. The algorithm correctly calculates all possible sums via iteration through nums2 and always updates min_sum if a smaller sum appears. This ensures the minimal index sum is chosen, not just the first pair found.