Maximum Product of Two Elements in an Array — Solution
Maximum Product of Two Elements in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Product of Two Elements in an Array is an easy coding problem on arrays, sorting and heap, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Sorting, Heap
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the array of integers nums, choose two different indices i and j and maximise (nums[i] - 1) * (nums[j] - 1).
Return that maximum value.
Example 1
Input: nums = [3,4,5,2]
Output: 12
Explanation: Picking 5 and 4 gives (5-1)×(4-1) = 12.
Example 2
Input: nums = [1,5,4,5]
Output: 16
Explanation: The two 5s sit at different indices.
Example 3
Input: nums = [3,7]
Output: 12
Constraints
2 <= nums.length <= 401 <= nums[i] <= 1000
Hints for Maximum Product of Two Elements in an Array
Hint 1
All values are at least 1, so
(x - 1)is never negative — the two largest values win.Hint 2
One pass carrying the largest and second largest is enough; no sort required.
Hint 3
Duplicated maxima are fine, since the indices only have to differ.
How to solve Maximum Product of Two Elements in an Array
All values are at least 1, so (x - 1) is non-negative and the two largest values give the maximum product.
Approach
- One pass keeping
firstandsecondlargest. - Return
(first - 1) * (second - 1).
Why it works
With non-negative factors the product is maximised by maximising both, and indices only need to differ, so equal maxima are fine.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- When updating, demote the old
firsttosecondbefore overwriting.
Reference solution
Python
def maxProduct(nums) -> int:
first = second = -1
for x in nums:
if x > first:
first, second = x, first
elif x > second:
second = x
return (first - 1) * (second - 1)Java
public static int maxProduct(int[] nums) {
int first = -1, second = -1;
for (int x : nums) {
if (x > first) {
second = first;
first = x;
} else if (x > second) {
second = x;
}
}
return (first - 1) * (second - 1);
}C++
int maxProduct(vector<int>& nums) {
int first = -1, second = -1;
for (int x : nums) {
if (x > first) {
second = first;
first = x;
} else if (x > second) {
second = x;
}
}
return (first - 1) * (second - 1);
}JavaScript
var maxProduct = function(nums) {
let first = -1, second = -1;
for (let i = 0; i < nums.length; i++) {
if (nums[i] > first) {
second = first;
first = nums[i];
} else if (nums[i] > second) {
second = nums[i];
}
}
return (first - 1) * (second - 1);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms