Skip to main content
Talentd

Maximum Product Pair With Target Sum - Solution & Explanation

Easy10 min read
Practice this problem

Problem Statement

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ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹

Approach Overview

Problem Overview: Given an array of integers and a target sum, find a pair of elements at different indices whose values add up to the target. Among all valid pairs, return the maximum product. If no pair exists, return -1.

Approach 1: Brute Force Pair Check (O(nĀ²) time, O(1) space)

Use two nested loops. The outer loop fixes index i, and the inner loop scans every j > i. For each pair, check whether nums[i] + nums[j] == target. If it matches, compute the product and update the running maximum. This approach needs no extra memory, and it works on unsorted input. Use it to confirm your logic, but do not submit it as the final answer when n is large.

Approach 2: Sort and Two Pointers (O(n log n) time, O(1) extra space)

Sort the array. Place one pointer at the start and one at the end. If the sum is less than the target, move the left pointer right. If the sum is greater, move the right pointer left. When the sum matches, record the product and move both pointers inward. Every candidate pair is visited once after sorting, so the scan is linear. The sort dominates the cost. This is the right choice when you are already working with sorted data or when memory must stay constant. See more on two pointers and sorting.

Approach 3: Hash Map Complement Lookup (O(n) time, O(n) space)

Walk the array once and store each value in a hash set or hash map as you go. For each element x, compute the complement target - x and check whether it already exists in the set. If it does, the pair (x, target - x) is valid, and its product is x * (target - x). Keep the maximum product seen. Each lookup takes average O(1), so the whole pass runs in O(n). Count occurrences when a value equals its own complement, because you need two distinct indices for that case. This is the approach that scales to large inputs. Learn more about hash tables.

Recommended for interviews: Interviewers expect the hash map solution. Start with the brute force to show you understand the pair condition. Then move to the hash map to show you can cut the cost from quadratic to linear. Mention the sort and two pointer option if the interviewer asks about memory limits or sorted input.

Solution

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 target/2 does not make the product larger, so each product is compared directly.

The complement of x is always y=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 pos to store the latest index of each value. Scan nums[i]=x from left to right and set y=target-x. If xneq y, y has already occurred, and xcdot y is greater than the best product so far, update the answer and place the larger value first so that nums[i]>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 nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair CheckO(nĀ²)O(1)Small inputs or verifying logic
Sort and Two PointersO(n log n)O(1) extraMemory constrained or array already sorted
Hash Map Complement LookupO(n)O(n)General case and interview default

Video Solutions (3)

Maximum Product Pair With Target Sum | LeetCode Biweekly Contest 193 | C++ Solution

Code Uncovered4:0379 views
Video 1 of 3

Frequently Asked Questions

Is Maximum Product Pair With Target Sum easy or hard?
It is an easy problem with an acceptance rate of about 43.5%. The core idea is a complement lookup, which you can learn quickly. The main challenge is handling duplicate values and making sure the two indices are distinct.
Maximum Product Pair With Target Sum Python solution?
In Python, create a set, loop through the array, and for each number check whether <code>target - num</code> is in the set. If it is, update the answer with <code>num * (target - num)</code>, then add <code>num</code> to the set. Return the maximum product, or -1 if no pair was found.
How to solve Maximum Product Pair With Target Sum in O(n)?
Iterate through the array while storing each value in a hash set. For every element <code>x</code>, compute <code>target - x</code> and check the set. If the complement exists, compute <code>x * (target - x)</code> and update the maximum. Handle the case where a value pairs with itself by requiring two occurrences.
What is the best approach for Maximum Product Pair With Target Sum?
The best approach is a hash map complement lookup. Scan the array once, store values you have seen, and check whether <code>target - x</code> already exists for each element <code>x</code>. This runs in O(n) time with O(n) extra space.
What data structure is used in Maximum Product Pair With Target Sum?
The optimal solution uses a hash set or hash map to store seen values for constant-time complement lookups. The sort and two pointer approach uses the array itself with pointers and needs no extra structure beyond sorting.
What is the time complexity of Maximum Product Pair With Target Sum?
The optimal hash map solution runs in O(n) time and O(n) space. The brute force version checks every pair in O(nĀ²) time with O(1) space. The sort and two pointer version runs in O(n log n) time with O(1) extra space.
Is Maximum Product Pair With Target Sum asked at Google, Amazon, or Meta?
This problem is tagged as General in the source data, so it is not tied to a specific company list. It tests hash map usage and pair search logic, which appear in many interviews at Google, Amazon, and Meta. Practice the hash map pattern because it transfers to many similar questions.

Ready to solve this problem?

Practice Maximum Product Pair With Target Sum with our built-in code editor and test cases.

Practice on FleetCode