Welcome to Subscribe On Youtube
4074. Maximum Product Pair With Target Sum
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] == targetnums[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}$.
-
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; } } -
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; } }; -
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 -
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 } -
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; }