Skip to content

3682. Minimum Index Sum of Common Elements πŸ”’

Description

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

Solutions

Solution 1: Hash Map

We initialize a variable \(\textit{ans}\) as infinity, representing the current minimum index sum, and use a hash map \(\textit{d}\) to store the first occurrence index of each element in array \(\textit{nums2}\).

Then we iterate through array \(\textit{nums1}\). For each element \(\textit{nums1}[i]\), if it exists in \(\textit{d}\), we calculate the index sum \(i + \textit{d}[\textit{nums1}[i]]\) and update \(\textit{ans}\).

Finally, if \(\textit{ans}\) is still infinity, it means no common element was found, so we return -1; otherwise, we return \(\textit{ans}\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def minimumSum(self, nums1: List[int], nums2: List[int]) -> int:
        d = {}
        for i, x in enumerate(nums2):
            if x not in d:
                d[x] = i
        ans = inf
        for i, x in enumerate(nums1):
            if x in d:
                ans = min(ans, i + d[x])
        return -1 if ans == inf else ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int minimumSum(int[] nums1, int[] nums2) {
        int n = nums1.length;
        final int inf = 1 << 30;
        Map<Integer, Integer> d = new HashMap<>();
        for (int i = 0; i < n; i++) {
            d.putIfAbsent(nums2[i], i);
        }
        int ans = inf;
        for (int i = 0; i < n; i++) {
            if (d.containsKey(nums1[i])) {
                ans = Math.min(ans, i + d.get(nums1[i]));
            }
        }
        return ans == inf ? -1 : ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minimumSum(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        const int inf = INT_MAX;
        unordered_map<int, int> d;
        for (int i = 0; i < n; i++) {
            if (!d.contains(nums2[i])) {
                d[nums2[i]] = i;
            }
        }
        int ans = inf;
        for (int i = 0; i < n; i++) {
            if (d.contains(nums1[i])) {
                ans = min(ans, i + d[nums1[i]]);
            }
        }
        return ans == inf ? -1 : ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func minimumSum(nums1 []int, nums2 []int) int {
    const inf = 1 << 30
    d := make(map[int]int)
    for i, x := range nums2 {
        if _, ok := d[x]; !ok {
            d[x] = i
        }
    }
    ans := inf
    for i, x := range nums1 {
        if j, ok := d[x]; ok {
            ans = min(ans, i + j)
        }
    }
    if ans == inf {
        return -1
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function minimumSum(nums1: number[], nums2: number[]): number {
    const n = nums1.length;
    const inf = 1 << 30;
    const d = new Map<number, number>();
    for (let i = 0; i < n; i++) {
        if (!d.has(nums2[i])) {
            d.set(nums2[i], i);
        }
    }
    let ans = inf;
    for (let i = 0; i < n; i++) {
        if (d.has(nums1[i])) {
            ans = Math.min(ans, i + (d.get(nums1[i]) as number));
        }
    }
    return ans === inf ? -1 : ans;
}

Comments