Skip to main content
Talentd

Minimum Index Sum of Common Elements - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash Table7 min read
Practice this problem

Problem Statement

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:

  • Common elements between nums1 and nums2 are 1 and 3.
  • For 3, [i, j] = [0, 1], giving an index sum of i + j = 1.
  • For 1, [i, j] = [2, 0], giving an index sum of i + j = 2.
  • The minimum index sum is 1.

Example 2:

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

Output: 2

Explanation:

  • Common elements between nums1 and nums2 are 1 and 2.
  • For 1, [i, j] = [1, 1], giving an index sum of i + j = 2.
  • For 2, [i, j] = [2, 0], giving an index sum of i + j = 2.
  • The minimum index sum is 2.

Example 3:

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

Output: -1

Explanation:

  • Since no common elements between nums1 and nums2, the output is -1.

 

Constraints:

  • 1 <= nums1.length == nums2.length <= 105
  • -105 <= nums1[i], nums2[i] <= 105

Approach Overview

Problem 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).

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ComparisonO(n * m)O(1)Small inputs or when extra memory cannot be used
Hash Map LookupO(n + m)O(n)General case; optimal for fast lookups and interview solutions

Frequently Asked Questions

Is Minimum Index Sum of Common Elements easy or hard?
The problem is typically classified as Medium. The logic is straightforward once you recognize the hash map optimization, but handling multiple results with the same minimum index sum requires careful tracking.
Minimum Index Sum of Common Elements Python/Java solution
Most implementations follow the same pattern across languages: build a dictionary or map for the first array, iterate through the second array, compute index sums, and track the minimum. This logic translates directly to Python dictionaries, Java HashMap, C++ unordered_map, Go maps, and TypeScript objects or Map.
How to solve Minimum Index Sum of Common Elements in O(n)?
Build a hash map from the first array mapping each element to its index. Iterate through the second array and check whether the element exists in the map. When it does, compute the index sum and maintain the minimum while collecting elements that match that minimum.
What is the best approach for Minimum Index Sum of Common Elements?
The hash map approach is the most efficient. Store each element from the first array with its index in a hash table, then scan the second array and compute index sums when matches appear. This reduces the complexity to O(n + m) time with O(n) extra space.
Is Minimum Index Sum of Common Elements asked at Google/Amazon/Meta?
Problems based on hash maps and array lookups frequently appear in interviews at companies like Amazon, Google, and Meta. Variations of this problem test whether candidates can replace nested loops with hash table lookups to reduce time complexity.
What data structure is used in Minimum Index Sum of Common Elements?
A hash table (hash map) is the primary data structure. It stores elements from one array with their indices, enabling constant-time lookups when scanning the second array.
What is the time complexity of Minimum Index Sum of Common Elements?
The optimal solution runs in O(n + m) time, where n and m are the lengths of the two arrays. Each array is traversed once and hash map lookups are O(1) on average. Space complexity is O(n) for storing the index map.

Ready to solve this problem?

Practice Minimum Index Sum of Common Elements with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays