Maximum Product of Two Elements in an Array solution and explanation
Google
9 more videos on this problem
Maximum Product of Two Elements in an Array | 2 Approaches | Leetcode-1464codestorywithMIK · 8:28 · 7K views
Leetcode Solution - 1464 Maximum Product of Two Elements in an ArrayJohn Leonardo · 2:28 · 2K views
Leetcode | 1464. Maximum Product of Two Elements in an Array | Easy | Java SolutionDeveloper Docs · 3:23 · 1K views
Leetcode 1464 – Maximum Product of Two Elements in an Array - Chi tiết nhiều cách giảiTiCungBim DSA · 13:25 · 1K views
1464. Maximum Product of Two Elements in an Array (python) (Leetcode Easy)Programming Live with Larry · 2:43 · 1K views
1464. Maximum Product of Two Elements in an Array - LeetCode | JavaAkshay Anil · 4:52 · 806 views
Maximum Product of Two Elements in an Array - LeetCode #1464 - Python, JavaScript, Java and C++CodingNinja · 7:16 · 632 views
Maximum Product of Two Elements in an Array C++ || Leetcode Problem Number 1464 #ZlozieCode #codeZlozie Code · 5:00 · 548 views
How to Solve "1464 Maximum Product of Two Elements in an Array" on LeetCode? - JavascriptBecoming A Better Dev (with David) · 7:49 · 255 views
Solving LeetCode 1464 Maximum Product of Two Elements in an Array | Amazon | EasyCode Harmony · 5:54 · 214 views
The problem
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.
def max_product(nums):
nums.sort()
return (nums[-1] - 1) * (nums[-2] - 1)
print(max_product([3, 4, 5, 2]))import java.util.Arrays;
public class Solution {
public int maxProduct(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
return (nums[n-1] - 1) * (nums[n-2] - 1);
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {3, 4, 5, 2};
System.out.println(solution.maxProduct(nums));
}
}#include <vector>
#include <algorithm>
#include <iostream>
int maxProduct(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
int n = nums.size();
return (nums[n-1] - 1) * (nums[n-2] - 1);
}
int main() {
std::vector<int> nums = {3, 4, 5, 2};
std::cout << maxProduct(nums) << std::endl;
return 0;
}function maxProduct(nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
return (nums[n - 1] - 1) * (nums[n - 2] - 1);
}
console.log(maxProduct([3, 4, 5, 2]));#include <stdio.h>
int maxProduct(int* nums, int numsSize) {
// Step 1: Sort the array
for (int i = 0; i < numsSize - 1; ++i) {
for (int j = 0; j < numsSize - i - 1; ++j) {
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
// Step 2: Calculate the maximum product of two largest numbers
int max1 = nums[numsSize - 1];
int max2 = nums[numsSize - 2];
return (max1 - 1) * (max2 - 1);
}
int main() {
int nums[] = {3, 4, 5, 2};
int numsSize = 4;
printf("%d\n", maxProduct(nums, numsSize));
return 0;
}using System;
public class Solution {
public int MaxProduct(int[] nums) {
Array.Sort(nums);
int n = nums.Length;
return (nums[n - 1] - 1) * (nums[n - 2] - 1);
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {3, 4, 5, 2};
Console.WriteLine(sol.MaxProduct(nums));
}
}Python's solution utilizes the built-in sort() method to sort the list and calculates the product for the last two elements after decrementing them.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) as the sort modifies the list in place.
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.
def max_product(nums):
max1, max2 = 0, 0
for num in nums:
if num > max1:
max2 = max1
max1 = num
elif num > max2:
max2 = num
return (max1 - 1) * (max2 - 1)
print(max_product([3, 4, 5, 2]))public class Solution {
public int maxProduct(int[] nums) {
int max1 = 0, max2 = 0;
for (int num : nums) {
if (num > max1) {
max2 = max1;
max1 = num;
} else if (num > max2) {
max2 = num;
}
}
return (max1 - 1) * (max2 - 1);
}
public static void main(String[] args) {
int[] nums = {3, 4, 5, 2};
Solution sol = new Solution();
System.out.println(sol.maxProduct(nums));
}
}#include <vector>
#include <iostream>
int maxProduct(std::vector<int>& nums) {
int max1 = 0, max2 = 0;
for (int num : nums) {
if (num > max1) {
max2 = max1;
max1 = num;
} else if (num > max2) {
max2 = num;
}
}
return (max1 - 1) * (max2 - 1);
}
int main() {
std::vector<int> nums = {3, 4, 5, 2};
std::cout << maxProduct(nums) << std::endl;
return 0;
}function maxProduct(nums) {
let max1 = 0, max2 = 0;
nums.forEach(num => {
if (num > max1) {
max2 = max1;
max1 = num;
} else if (num > max2) {
max2 = num;
}
});
return (max1 - 1) * (max2 - 1);
}
console.log(maxProduct([3, 4, 5, 2]));#include <stdio.h>
int maxProduct(int* nums, int numsSize) {
int max1 = 0, max2 = 0;
for (int i = 0; i < numsSize; ++i) {
if (nums[i] > max1) {
max2 = max1;
max1 = nums[i];
} else if (nums[i] > max2) {
max2 = nums[i];
}
}
return (max1 - 1) * (max2 - 1);
}
int main() {
int nums[] = {3, 4, 5, 2};
int numsSize = 4;
printf("%d\n", maxProduct(nums, numsSize));
return 0;
}using System;
public class Solution {
public int MaxProduct(int[] nums) {
int max1 = 0, max2 = 0;
foreach (int num in nums) {
if (num > max1) {
max2 = max1;
max1 = num;
} else if (num > max2) {
max2 = num;
}
}
return (max1 - 1) * (max2 - 1);
}
public static void Main() {
int[] nums = {3, 4, 5, 2};
Solution sol = new Solution();
Console.WriteLine(sol.MaxProduct(nums));
}
}In Python, the two maximums are determined by tracking the largest and second-largest numbers during a single traversal of the list. This process avoids the need to sort and efficiently produces the maximum product.
Time Complexity: O(n). Space Complexity: O(1).
Approach 3: Default Approach
function maxProduct(nums: number[]): number {
const n = nums.length;
for (let i = 0; i < 2; i++) {
let maxIdx = i;
for (let j = i + 1; j < n; j++) {
if (nums[j] > nums[maxIdx]) {
maxIdx = j;
}
}
[nums[i], nums[maxIdx]] = [nums[maxIdx], nums[i]];
}
return (nums[0] - 1) * (nums[1] - 1);
}func maxProduct(nums []int) int {
ans := 0
for i, a := range nums {
for _, b := range nums[i+1:] {
t := (a - 1) * (b - 1)
if ans < t {
ans = t
}
}
}
return ans
}impl Solution {
pub fn max_product(nums: Vec<i32>) -> i32 {
let mut max = 0;
let mut submax = 0;
for &num in nums.iter() {
if num > max {
submax = max;
max = num;
} else if num > submax {
submax = num;
}
}
(max - 1) * (submax - 1)
}
}class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function maxProduct($nums) {
$max = 0;
$submax = 0;
for ($i = 0; $i < count($nums); $i++) {
if ($nums[$i] > $max) {
$submax = $max;
$max = $nums[$i];
} elseif ($nums[$i] > $submax) {
$submax = $nums[$i];
}
}
return ($max - 1) * ($submax - 1);
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sorting Maximum Two Elements | Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) as the sort modifies the list in place. |
| Approach 2: Single Pass for Maximum Two Elements | Time Complexity: O(n). Space Complexity: O(1). |
| Default Approach | – |
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 |
Frequently asked questions
Is Maximum Product of Two Elements in an Array easy or hard?
Maximum Product of Two Elements in an Array is classified as an Easy problem. The main challenge is recognizing that only the two largest numbers affect the result. Once that insight is clear, the solution becomes a straightforward single-pass scan.
Maximum Product of Two Elements in an Array Python/Java solution
In Python or Java, the most efficient solution iterates once through the array while tracking the largest and second-largest numbers. After the loop finishes, compute (max1 - 1) * (max2 - 1). This implementation runs in O(n) time and uses O(1) extra space.
How to solve Maximum Product of Two Elements in an Array in O(n)?
Iterate through the array once while maintaining two variables: the largest and second largest values seen so far. Update these values whenever a larger element appears. After the traversal, compute the result using (max1 - 1) * (max2 - 1). This avoids sorting and keeps the runtime linear.
What is the best approach for Maximum Product of Two Elements in an Array?
The best approach is a single-pass scan that tracks the largest and second-largest numbers while iterating through the array. This method runs in O(n) time and O(1) space because it only keeps two variables. After identifying the two maximum values, compute (max1 - 1) * (max2 - 1).
Is Maximum Product of Two Elements in an Array asked at Google/Amazon/Meta?
Variants of this problem appear in coding interviews at major tech companies because it tests array scanning, comparison logic, and identifying top elements efficiently. Interviewers often expect the O(n) solution rather than a sorting-based approach.
What data structure is used in Maximum Product of Two Elements in an Array?
The optimal solution does not require any special data structure beyond simple variables. Alternative implementations may use sorting algorithms or a heap (priority queue) to retrieve the two largest elements. The heap approach is useful when repeatedly querying maximum elements.
What is the time complexity of Maximum Product of Two Elements in an Array?
The optimal solution runs in O(n) time using a single pass to track the two largest numbers. A simpler alternative sorts the array, which takes O(n log n) time. Both approaches use constant extra space except for possible recursion stack usage during sorting.