You are given two integer arrays nums1 and nums2 of equal length n.
We define a pair of indices (i, j) as a good pair if nums1[i] == nums2[j].
Return the minimum index sum i + j among all possible good pairs. If no such pairs exist, return -1.
Example 1:
Input: nums1 = [3,2,1], nums2 = [1,3,1]
Output: 1
Explanation:
nums1 and nums2 are 1 and 3.[i, j] = [0, 1], giving an index sum of i + j = 1.[i, j] = [2, 0], giving an index sum of i + j = 2.Example 2:
Input: nums1 = [5,1,2], nums2 = [2,1,3]
Output: 2
Explanation:
nums1 and nums2 are 1 and 2.[i, j] = [1, 1], giving an index sum of i + j = 2.[i, j] = [2, 0], giving an index sum of i + j = 2.Example 3:
Input: nums1 = [6,4], nums2 = [7,8]
Output: -1
Explanation:
nums1 and nums2, the output is -1.
Constraints:
1 <= nums1.length == nums2.length <= 105-105 <= nums1[i], nums2[i] <= 105Problem Overview: You are given two arrays of elements. The task is to find the common element(s) whose index sum (index in the first array + index in the second array) is minimum. If multiple elements share the same smallest index sum, return all of them.
Approach 1: Brute Force Comparison (O(n * m) time, O(1) space)
The most direct method checks every pair of elements from the two arrays. Iterate through the first array, and for each element scan the second array to see if it appears there. When a match is found, compute the index sum and track the minimum encountered so far. Maintain a result list for elements with that minimum sum.
This approach requires nested loops and repeated comparisons, which leads to O(n * m) time complexity. Space usage stays O(1) aside from the result list. It works for small inputs but becomes slow as the arrays grow.
Approach 2: Hash Map Lookup (O(n + m) time, O(n) space)
The optimal approach uses a hash table to eliminate repeated searches. First, iterate through the first array and store each element with its index in a hash map. Then iterate through the second array and check whether each element exists in the map using constant-time lookup.
When a common element appears, compute the index sum using the stored index from the first array and the current index from the second array. Track the smallest sum and update the result list accordingly. Because each array is processed once and lookups are O(1), the total runtime becomes O(n + m) with O(n) additional space.
This method is a classic application of combining array traversal with hash-based indexing. The key insight is replacing repeated searches with constant-time lookups.
Recommended for interviews: The hash map approach is what interviewers expect. It demonstrates your ability to trade space for speed and use efficient lookups. Mentioning the brute force solution first shows you understand the baseline complexity, but implementing the hash table optimization proves you can reduce the runtime from O(n * m) to O(n + m).
We initialize a variable ans as infinity, representing the current minimum index sum, and use a hash map d to store the first occurrence index of each element in array nums2.
Then we iterate through array nums1. For each element nums1[i], if it exists in d, we calculate the index sum i + d[nums1[i]] and update ans.
Finally, if ans is still infinity, it means no common element was found, so we return -1; otherwise, we return ans.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Comparison | O(n * m) | O(1) | Small inputs or when extra memory cannot be used |
| Hash Map Lookup | O(n + m) | O(n) | General case; optimal for fast lookups and interview solutions |
Practice Minimum Index Sum of Common Elements with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor