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.

Description Hints 4 Solution

3682. Minimum Index Sum of Common Elements

Medium77.5% acceptancePremium elsewhere, free here

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 <= 10⁵
-10⁵ <= nums1[i], nums2[i] <= 10⁵

Topics

Array Hash Table

Hints open one at a time

Hint 1

Build a hash map pos1 that stores, for each value in nums1, the smallest index where it appears.

Hint 2

Iterate through nums2. For each index j, if nums2[j] exists in pos1, compute pos1[nums2[j]] + j.

Hint 3

Track the minimum index sum across all such matches.

Hint 4

If no common element is found, return -1.

Still stuck?Read the written solution.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[3,2,1]
[1,3,1]

Input

[5,1,2]
[2,1,3]

Input

[6,4]
[7,8]

Your code is saved on this device.Solution