Skip to content

4074. Maximum Product Pair With Target Sum

DifficultyEasy

Description

You are given an integer array nums and an integer target.

A pair of distinct indices (i, j) is valid if:

  • nums[i] + nums[j] == target
  • nums[i] > nums[j]

Return a valid pair [i, j] whose product nums[i] * nums[j] is maximum among all valid pairs. If no valid pair exists, return [-1, -1].

If multiple valid pairs achieve the maximum product, you may return any of them.

 

Example 1:

Input: nums = [1,2,3,4], target = 5

Output: [2,1]

Explanation:

There are 2 valid pairs:

No. (i, j) nums[i] nums[j] Sum Product
1 (3, 0) 4 1 5 4
2 (2, 1) 3 2 5 6

Both pairs sum to 5 and satisfy nums[i] > nums[j]. The second pair has the larger product, 3 * 2 = 6, so the answer is [2, 1].

Example 2:

Input: nums = [-3,-1,4,2], target = 1

Output: [3,1]

Explanation:

There are 2 valid pairs:

No. (i, j) nums[i] nums[j] Sum Product
1 (2, 0) 4 -3 1 -12
2 (3, 1) 2 -1 1 -2

Since -2 > -12, the pair at indices (3, 1) is chosen and the answer is [3, 1].

Example 3:

Input: nums = [3,3,5], target = 6

Output: [-1,-1]

Explanation:

​​​​​​​No valid pair exists, since nums[0] and nums[1] sum to 6 but are equal.

 

Constraints:

  • 2 <= nums.length <= 100
  • -100 <= nums[i], target <= 100​​​​​​​

Solutions

Solution 1: Hash Map

Thinking

With \(n\le 100\), checking every pair of indices is already fast enough. Negative values need separate care: once the sum is fixed, moving the two numbers closer to \(\textit{target}/2\) does not make the product larger, so each product is compared directly.

The complement of \(x\) is always \(y=\textit{target}-x\). A valid pair also requires the two values to be different, so the case \(x=y\) can be skipped.

The product depends only on those two values. While scanning from left to right, a hash map stores the latest index of each value; when \(x\) is seen, look up \(y\) and keep the pair with the larger product.

Use a hash map \(\textit{pos}\) to store the latest index of each value. Scan \(\textit{nums}[i]=x\) from left to right and set \(y=\textit{target}-x\). If \(x\neq y\), \(y\) has already occurred, and \(x\cdot y\) is greater than the best product so far, update the answer and place the larger value first so that \(\textit{nums}[i]>\textit{nums}[j]\). If no valid pair is found, the answer stays \([-1,-1]\).

The time complexity is \(O(n)\) and the space complexity is \(O(n)\), where \(n\) is the length of \(\textit{nums}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
from math import inf


class Solution:
    def maxProductPair(self, nums: list[int], target: int) -> list[int]:
        pos = {}
        mx = -inf
        ans = [-1, -1]
        for i, x in enumerate(nums):
            y = target - x
            if x != y and x * y > mx and y in pos:
                j = pos[y]
                mx = x * y
                ans = [i, j] if x > y else [j, i]
            pos[x] = i
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int[] maxProductPair(int[] nums, int target) {
        Map<Integer, Integer> pos = new HashMap<>();
        int mx = Integer.MIN_VALUE;
        int[] ans = {-1, -1};
        for (int i = 0; i < nums.length; ++i) {
            int x = nums[i], y = target - x;
            if (x != y && x * y > mx && pos.containsKey(y)) {
                int j = pos.get(y);
                mx = x * y;
                ans = x > y ? new int[] {i, j} : new int[] {j, i};
            }
            pos.put(x, i);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> maxProductPair(vector<int>& nums, int target) {
        unordered_map<int, int> pos;
        int mx = INT_MIN;
        vector<int> ans = {-1, -1};
        for (int i = 0; i < nums.size(); ++i) {
            int x = nums[i], y = target - x;
            if (x != y && x * y > mx && pos.contains(y)) {
                int j = pos[y];
                mx = x * y;
                ans = x > y ? vector<int>{i, j} : vector<int>{j, i};
            }
            pos[x] = i;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func maxProductPair(nums []int, target int) []int {
    pos := map[int]int{}
    mx := -int(^uint(0)>>1) - 1
    ans := []int{-1, -1}
    for i, x := range nums {
        y := target - x
        if j, ok := pos[y]; x != y && ok && x*y > mx {
            mx = x * y
            if x > y {
                ans = []int{i, j}
            } else {
                ans = []int{j, i}
            }
        }
        pos[x] = i
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function maxProductPair(nums: number[], target: number): number[] {
    const pos = new Map<number, number>();
    let mx = -Infinity;
    let ans = [-1, -1];
    for (let i = 0; i < nums.length; ++i) {
        const x = nums[i],
            y = target - x;
        if (x !== y && x * y > mx && pos.has(y)) {
            const j = pos.get(y)!;
            mx = x * y;
            ans = x > y ? [i, j] : [j, i];
        }
        pos.set(x, i);
    }
    return ans;
}

Comments