Maximum Product of Three Numbers solution and explanation
TCS
Infosys
Google
9 more videos on this problem
628. Maximum Product of Three Numbers | LEETCODE EASY | SORTING | LOGICcode Explainer · 4:55 · 13K views
Maximum Product of Three Numbers Walkthrough (Leetcode #628)Programmer Mitch · 23:57 · 5K views
628. Maximum Product of Three Numbers (LeetCode)hakunamatasq · 3:05 · 2K views
MAXIMUM PRODUCT OF THREE NUMBERS ( LEETCODE 628 ) Solution in Java | LEETCODE | PROBLEM SOLVINGEconomic Coder · 14:37 · 2K views
Maximum Product of Three Numbers | LeetCode 628 | Top Placement Question | optimal Solution C++ |Onlycodes · 7:21 · 1K views
Maximum Product of Three Numbers || Approach 2 || Leetcode 628Code with Newton · 13:42 · 1K views
Maximum Product of Three Numbers | Leetcode 628 | Amazon Google Facebook interview questionSuper Lazy Coder · 11:29 · 906 views
Leetcode: 628. Maximum Product of Three NumbersMath Geeks · 4:58 · 866 views
628. Maximum Product of Three Numbers (Leetcode Easy)Programming Live with Larry · 10:39 · 402 views
LeetCode #628 | Maximum Product of Three Numbers | Efficient Solution | Problem Solving | LVS LogicsLVS Logics · 4:28 · 347 views
The problem
Given an integer array nums, find three numbers whose product is maximum and return the maximum product.
Example 1:
Input: nums = [1,2,3] Output: 6
Example 2:
Input: nums = [1,2,3,4] Output: 24
Example 3:
Input: nums = [-1,-2,-3] Output: -6
Constraints:
3 <= nums.length <= 104-1000 <= nums[i] <= 1000
Approach overview
Problem Overview: You are given an integer array and must return the maximum product possible using any three numbers. The tricky part is handling negative values. Two large negative numbers multiplied together produce a positive number, which can sometimes beat the product of the three largest values.
Approach 1: Sorting for Maximum Product (O(n log n) time, O(1) space)
Sort the array and evaluate the only two combinations that can produce the maximum result. First, the product of the three largest numbers at the end of the sorted array. Second, the product of the two smallest numbers (which may be large negatives) with the largest number. After sorting, both combinations are available with direct index access, so you simply compute both and return the larger value. The logic relies on properties of signed multiplication and is easy to reason about, which makes it a common baseline solution when working with sorting problems on an array. The tradeoff is the O(n log n) sorting cost.
Approach 2: Single Pass Min/Max Tracking (O(n) time, O(1) space)
This approach avoids sorting by tracking the three largest numbers and the two smallest numbers during a single iteration of the array. Maintain variables for max1, max2, max3 (largest values) and min1, min2 (smallest values). For each element, update these trackers using simple comparisons. After one pass, compute two candidate products: max1 * max2 * max3 and max1 * min1 * min2. The first represents the top three positives, while the second captures the case where two negatives produce a large positive. This method uses constant memory and linear traversal, making it the optimal solution for large inputs and a classic pattern in math-based array optimization problems.
Recommended for interviews: The single-pass approach is what interviewers usually expect because it demonstrates awareness of edge cases with negative numbers while keeping the runtime at O(n). Mentioning the sorting solution first shows clear reasoning and correctness, but implementing the O(n) min/max tracking method shows stronger algorithmic thinking and attention to performance.
Approach 1: Sorting for Maximum Product
This approach involves sorting the array, and then choosing the maximum product by examining either the product of the three largest numbers or the product of the two smallest numbers and the largest number.
def maximumProduct(nums):
nums.sort()
return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * nums[-1])
print(maximumProduct([1, 2, 3, 4]))import java.util.Arrays;
public class MaxProduct {
public static int maximumProduct(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
return Math.max(nums[n-1] * nums[n-2] * nums[n-3], nums[0] * nums[1] * nums[n-1]);
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4};
System.out.println(maximumProduct(nums));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int maximumProduct(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
int n = nums.size();
return std::max(nums[n-1] * nums[n-2] * nums[n-3], nums[0] * nums[1] * nums[n-1]);
}
int main() {
std::vector<int> nums = {1, 2, 3, 4};
std::cout << maximumProduct(nums) << std::endl;
return 0;
}function maximumProduct(nums) {
nums.sort((a, b) => a - b);
let n = nums.length;
return Math.max(nums[n-1] * nums[n-2] * nums[n-3], nums[0] * nums[1] * nums[n-1]);
}
console.log(maximumProduct([1, 2, 3, 4]));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int maximumProduct(int* nums, int numsSize){
qsort(nums, numsSize, sizeof(int), compare);
int a = nums[numsSize - 1] * nums[numsSize - 2] * nums[numsSize - 3];
int b = nums[0] * nums[1] * nums[numsSize - 1];
return a > b ? a : b;
}
int main() {
int arr[] = {1, 2, 3, 4};
int size = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", maximumProduct(arr, size));
return 0;
}using System;
public class MaxProduct {
public static int MaximumProduct(int[] nums) {
Array.Sort(nums);
int n = nums.Length;
return Math.Max(nums[n-1] * nums[n-2] * nums[n-3], nums[0] * nums[1] * nums[n-1]);
}
public static void Main() {
int[] nums = {1, 2, 3, 4};
Console.WriteLine(MaximumProduct(nums));
}
}In Python, we sort the list, then determine the maximal product by comparing the product of the three largest numbers and the product of the two smallest numbers with the largest number.
Time Complexity: O(n log n), where n is the length of the list due to sorting.
Space Complexity: O(1).
Approach 2: Single Pass Approach
This approach involves finding the largest three and smallest two numbers in a single traversal of the array. This avoids sorting and gives a more optimal solution for time complexity.
def maximumProduct(nums):
max1 = max2 = max3 = float('-inf')
min1 = min2 = float('inf')
for num in nums:
if num > max1:
max3 = max2
max2 = max1
max1 = num
elif num > max2:
max3 = max2
max2 = num
elif num > max3:
max3 = num
if num < min1:
min2 = min1
min1 = num
elif num < min2:
min2 = num
return max(max1 * max2 * max3, min1 * min2 * max1)
print(maximumProduct([1, 2, 3, 4]))public class MaxProductSinglePass {
public static int maximumProduct(int[] nums) {
int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
for (int num : nums) {
if (num > max1) {
max3 = max2;
max2 = max1;
max1 = num;
} else if (num > max2) {
max3 = max2;
max2 = num;
} else if (num > max3) {
max3 = num;
}
if (num < min1) {
min2 = min1;
min1 = num;
} else if (num < min2) {
min2 = num;
}
}
return Math.max(max1 * max2 * max3, min1 * min2 * max1);
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4};
System.out.println(maximumProduct(nums));
}
}#include <iostream>
#include <vector>
#include <limits.h>
int maximumProduct(std::vector<int>& nums) {
int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
int min1 = INT_MAX, min2 = INT_MAX;
for (int num : nums) {
if (num > max1) {
max3 = max2;
max2 = max1;
max1 = num;
} else if (num > max2) {
max3 = max2;
max2 = num;
} else if (num > max3) {
max3 = num;
}
if (num < min1) {
min2 = min1;
min1 = num;
} else if (num < min2) {
min2 = num;
}
}
return std::max(max1*max2*max3, min1*min2*max1);
}
int main() {
std::vector<int> nums = {1, 2, 3, 4};
std::cout << maximumProduct(nums) << std::endl;
return 0;
}function maximumProduct(nums) {
let max1 = -Infinity, max2 = -Infinity, max3 = -Infinity;
let min1 = Infinity, min2 = Infinity;
for (let num of nums) {
if (num > max1) {
max3 = max2;
max2 = max1;
max1 = num;
} else if (num > max2) {
max3 = max2;
max2 = num;
} else if (num > max3) {
max3 = num;
}
if (num < min1) {
min2 = min1;
min1 = num;
} else if (num < min2) {
min2 = num;
}
}
return Math.max(max1 * max2 * max3, min1 * min2 * max1);
}
console.log(maximumProduct([1, 2, 3, 4]));#include <stdio.h>
#include <limits.h>
int maximumProduct(int* nums, int numsSize) {
int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
int min1 = INT_MAX, min2 = INT_MAX;
for (int i = 0; i < numsSize; i++) {
if (nums[i] > max1) {
max3 = max2;
max2 = max1;
max1 = nums[i];
} else if (nums[i] > max2) {
max3 = max2;
max2 = nums[i];
} else if (nums[i] > max3) {
max3 = nums[i];
}
if (nums[i] < min1) {
min2 = min1;
min1 = nums[i];
} else if (nums[i] < min2) {
min2 = nums[i];
}
}
return max1*max2*max3 > min1*min2*max1 ? max1*max2*max3 : min1*min2*max1;
}
int main() {
int nums[] = {1, 2, 3, 4};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", maximumProduct(nums, size));
return 0;
}using System;
public class MaxProductSinglePass {
public static int MaximumProduct(int[] nums) {
int max1 = int.MinValue, max2 = int.MinValue, max3 = int.MinValue;
int min1 = int.MaxValue, min2 = int.MaxValue;
foreach (int num in nums) {
if (num > max1) {
max3 = max2;
max2 = max1;
max1 = num;
} else if (num > max2) {
max3 = max2;
max2 = num;
} else if (num > max3) {
max3 = num;
}
if (num < min1) {
min2 = min1;
min1 = num;
} else if (num < min2) {
min2 = num;
}
}
return Math.Max(max1 * max2 * max3, min1 * min2 * max1);
}
public static void Main() {
int[] nums = {1, 2, 3, 4};
Console.WriteLine(MaximumProduct(nums));
}
}This solution captures the top three largest and two smallest values during one loop through the list, allowing us to calculate and compare the products efficiently.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 3: Sorting + Case Analysis
First, we sort the array nums, and then discuss two cases:
- If
numscontains all non-negative or all non-positive numbers, the answer is the product of the last three numbers, i.e.,nums[n-1] times nums[n-2] times nums[n-3]; - If
numscontains both positive and negative numbers, the answer could be the product of the two smallest negative numbers and the largest positive number, i.e.,nums[n-1] times nums[0] times nums[1], or the product of the last three numbers, i.e.,nums[n-1] times nums[n-2] times nums[n-3].
Finally, return the maximum of the two cases.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array nums.
function maximumProduct(nums: number[]): number {
nums.sort((a, b) => a - b);
const n = nums.length;
const a = nums[n - 1] * nums[n - 2] * nums[n - 3];
const b = nums[n - 1] * nums[0] * nums[1];
return Math.max(a, b);
}func maximumProduct(nums []int) int {
sort.Ints(nums)
n := len(nums)
a := nums[n-1] * nums[n-2] * nums[n-3]
b := nums[n-1] * nums[0] * nums[1]
if a > b {
return a
}
return b
}Approach 4: Single Pass
We can avoid sorting the array by maintaining five variables: mi1 and mi2 represent the two smallest numbers in the array, while mx1, mx2, and mx3 represent the three largest numbers in the array.
Finally, return max(mi1 times mi2 times mx1, mx1 times mx2 times mx3).
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
function maximumProduct(nums: number[]): number {
const inf = 1 << 30;
let mi1 = inf,
mi2 = inf;
let mx1 = -inf,
mx2 = -inf,
mx3 = -inf;
for (const x of nums) {
if (x < mi1) {
mi2 = mi1;
mi1 = x;
} else if (x < mi2) {
mi2 = x;
}
if (x > mx1) {
mx3 = mx2;
mx2 = mx1;
mx1 = x;
} else if (x > mx2) {
mx3 = mx2;
mx2 = x;
} else if (x > mx3) {
mx3 = x;
}
}
return Math.max(mi1 * mi2 * mx1, mx1 * mx2 * mx3);
}func maximumProduct(nums []int) int {
const inf = 1 << 30
mi1, mi2 := inf, inf
mx1, mx2, mx3 := -inf, -inf, -inf
for _, x := range nums {
if x < mi1 {
mi1, mi2 = x, mi1
} else if x < mi2 {
mi2 = x
}
if x > mx1 {
mx1, mx2, mx3 = x, mx1, mx2
} else if x > mx2 {
mx2, mx3 = x, mx2
} else if x > mx3 {
mx3 = x
}
}
return max(mi1*mi2*mx1, mx1*mx2*mx3)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting for Maximum Product | Time Complexity: |
| Single Pass Approach | Time Complexity: |
| Sorting + Case Analysis | – |
| Single Pass | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting for Maximum Product | O(n log n) | O(1) | Simple and readable approach when sorting is acceptable |
| Single Pass Min/Max Tracking | O(n) | O(1) | Optimal solution for large arrays or interview scenarios |
Frequently asked questions
Is Maximum Product of Three Numbers easy or hard?
Maximum Product of Three Numbers is classified as an Easy problem. The main challenge is recognizing that two negative numbers can produce a larger product than three positive numbers, which leads to checking both candidate combinations.
Maximum Product of Three Numbers Python/Java solution
Python and Java solutions typically implement either sorting or the single-pass approach. The sorting solution uses built-in sort functions and checks two candidate products, while the optimal implementation tracks three maximum and two minimum values during one iteration.
How to solve Maximum Product of Three Numbers in O(n)?
Traverse the array once while keeping track of the three largest numbers and the two smallest numbers. After the traversal, compute the product of the three largest values and compare it with the product of the largest value and the two smallest values. The maximum of these two results is the answer.
What is the best approach for Maximum Product of Three Numbers?
The best approach is the single-pass min/max tracking method with O(n) time and O(1) space. It scans the array once while maintaining the three largest numbers and the two smallest numbers. This works because the maximum product can come from either the three largest values or the largest value combined with two negative numbers.
Is Maximum Product of Three Numbers asked at Google/Amazon/Meta?
Maximum Product of Three Numbers appears in coding interview preparation lists and practice sets for companies like Amazon and Google. The problem tests understanding of edge cases with negative numbers and efficient single-pass array processing.
What data structure is used in Maximum Product of Three Numbers?
The problem primarily uses arrays along with simple variable tracking for minimum and maximum values. No advanced data structures are required, but understanding array traversal and value comparisons is essential.
What is the time complexity of Maximum Product of Three Numbers?
The optimal solution runs in O(n) time using a single pass through the array while tracking minimum and maximum values. A simpler alternative sorts the array first, which results in O(n log n) time complexity.