Maximum Product of Two Elements in an Array - Solution & Explanation
Problem Statement
nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1).
Example 1:
Input: nums = [3,4,5,2] Output: 12 Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12.
Example 2:
Input: nums = [1,5,4,5] Output: 16 Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16.
Example 3:
Input: nums = [3,7] Output: 12
Constraints:
2 <= nums.length <= 5001 <= nums[i] <= 10^3
Approach Overview
Problem Overview: You are given an integer array nums. Choose two different indices i and j such that the value (nums[i] - 1) * (nums[j] - 1) is maximized. The task reduces to finding the two largest numbers in the array because subtracting 1 from both still preserves the order of maximum values.
Approach 1: Sorting Maximum Two Elements (Time: O(n log n), Space: O(1) or O(log n))
Sort the array and use the last two elements since they are the largest values. After sorting, compute (nums[n-1] - 1) * (nums[n-2] - 1). This approach relies on sorting to organize values so the largest elements appear at the end. The implementation is short and reliable because sorting handles all ordering logic. Use this method when code simplicity matters more than strict linear time performance.
Approach 2: Single Pass for Maximum Two Elements (Time: O(n), Space: O(1))
Iterate through the array once while tracking the largest and second largest values. For each number, compare it with the current maximum; if it becomes the new maximum, shift the previous maximum to second place. Otherwise update the second maximum when appropriate. After the loop, compute (max1 - 1) * (max2 - 1). This method uses the core idea behind many array scanning problems: maintain running candidates during a single traversal. It avoids sorting entirely and achieves optimal linear time.
Approach 3: Max Heap (Priority Queue) (Time: O(n log n) or O(n + log n), Space: O(n))
Insert all elements into a max heap and extract the top two values. A heap (priority queue) always keeps the largest element accessible at the root. After removing the two largest values, compute the product using the required formula. This approach is helpful when the problem extends to repeatedly retrieving largest elements, though it is unnecessary overhead for a single query.
Recommended for interviews: The single-pass solution is what interviewers usually expect. It demonstrates that you recognized the key observation: only the two largest numbers matter. The sorting approach still shows correct reasoning and is acceptable for an easy problem, but the O(n) scan highlights stronger algorithmic awareness and space efficiency.
Approach 1: Approach 1: Sorting Maximum Two Elements
One effective way to find the maximum product is by first sorting the array, then selecting the two largest elements, which will naturally be at the end of the sorted list. The product of their decremented values will provide the result.
The C implementation sorts the array using a simple bubble sort. Once sorted, the two largest elements are accessed directly using their indices at the end of the array. After computing the product of their decremented values, the result is returned.
Complexity
Time Complexity: O(n^2) due to the bubble sort implementation. Space Complexity: O(1) since no extra space is used.
Approach 2: Approach 2: Single Pass for Maximum Two Elements
This approach finds the two largest numbers in a single pass without sorting. By iterating over the array, we track the largest and second-largest numbers. With these two numbers, we compute the maximum product efficiently.
The C implementation maintains two variables to track the largest and second-largest numbers encountered. Each element is compared in sequence, and the variables are adjusted appropriately to find these numbers without sorting the full array.
Complexity
Time Complexity: O(n) because we pass through the array just once. Space Complexity: O(1) as no additional space is required.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sorting Maximum Two Elements | Time Complexity: O(n^2) due to the bubble sort implementation. Space Complexity: O(1) since no extra space is used. |
| Approach 2: Single Pass for Maximum Two Elements | Time Complexity: O(n) because we pass through the array just once. Space Complexity: O(1) as no additional space is required. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting Maximum Two Elements | O(n log n) | O(1) or O(log n) | When simplicity matters and sorting is acceptable |
| Single Pass Tracking Two Maximums | O(n) | O(1) | Best general solution; optimal for interviews and large arrays |
| Max Heap (Priority Queue) | O(n log n) or O(n + log n) | O(n) | Useful when repeatedly extracting largest elements |
Video Solution
Maximum Product of Two Elements in an Array | 2 Approaches | Leetcode-1464 • codestorywithMIK • 7,293 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Product of Two Elements in an Array easy or hard?
Maximum Product of Two Elements in an Array Python/Java solution
How to solve Maximum Product of Two Elements in an Array in O(n)?
What is the best approach for Maximum Product of Two Elements in an Array?
Is Maximum Product of Two Elements in an Array asked at Google/Amazon/Meta?
What data structure is used in Maximum Product of Two Elements in an Array?
What is the time complexity of Maximum Product of Two Elements in an Array?
Ready to solve this problem?
Practice Maximum Product of Two Elements in an Array with our built-in code editor and test cases.
Practice on FleetCode