Approach Summary
Track both max and min products ending at i (negatives can flip sign). maxProd[i] = max(nums[i], maxPrev×nums[i], minPrev×nums[i]).
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Brute Force (All Subarrays) | O(n²) | O(1) | Examine product of every contiguous subarray using nested loops. |
| 2 Approach 2: Prefix and Suffix Two-Way Traversal (Optimal) | O(n) | O(1) | Scan forward and backward accumulating products, resetting to 1 whenever reaching zero. |
Step 1: Baseline
Approach 1: Brute Force (All Subarrays)
Time: O(n²)
Space: O(1)
Fix start index i and expand end index j, computing the cumulative product `prod *= nums[j]`. Keep track of the highest product encountered. While straightforward, computing all n*(n+1)/2 subarrays is too slow for large inputs.
Approach 1: Brute Force (All Subarrays) Implementation
Approach 1: Brute Force (All Subarrays)
class Solution {
public int maxProduct(int[] nums) {
int maxProd = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
int prod = 1;
for (int j = i; j < nums.length; j++) {
prod *= nums[j];
maxProd = Math.max(maxProd, prod);
}
}
return maxProd;
}
}class Solution {
public:
int maxProduct(vector<int>& nums) {
int maxProd = INT_MIN;
int n = nums.size();
for (int i = 0; i < n; i++) {
int prod = 1;
for (int j = i; j < n; j++) {
prod *= nums[j];
maxProd = max(maxProd, prod);
}
}
return maxProd;
}
};def max_product(nums: list[int]) -> int:
max_prod = float('-inf')
n = len(nums)
for i in range(n):
prod = 1
for j in range(i, n):
prod *= nums[j]
max_prod = max(max_prod, prod)
return int(max_prod)function maxProduct(nums) {
let maxProd = -Infinity;
const n = nums.length;
for (let i = 0; i < n; i++) {
let prod = 1;
for (let j = i; j < n; j++) {
prod *= nums[j];
maxProd = Math.max(maxProd, prod);
}
}
return maxProd;
} Step 2: Most Optimized
Approach 2: Prefix and Suffix Two-Way Traversal (Optimal)
Time: O(n)
Space: O(1)
If an array has no zeros, any odd number of negatives means either the prefix before the last negative or the suffix after the first negative is the maximum positive product. If there are zeros, they act as boundaries dividing the array into independent segments. By traversing forward (prefix) and backward (suffix) and resetting the multiplier to 1 after every 0, we cover all maximal prefix and suffix candidates in two simple passes.
Approach 2: Prefix and Suffix Two-Way Traversal (Optimal) Implementation
Approach 2: Prefix and Suffix Two-Way Traversal (Optimal)
class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
int prefix = 1;
int maximumProduct = Integer.MIN_VALUE;
int suffix = 1;
for (int i = 0; i < n; i++) {
prefix *= nums[i];
maximumProduct = Math.max(maximumProduct, prefix);
if (nums[i] == 0) {
prefix = 1;
}
}
for (int i = n - 1; i >= 0; i--) {
suffix *= nums[i];
maximumProduct = Math.max(maximumProduct, suffix);
if (nums[i] == 0) {
suffix = 1;
}
}
return maximumProduct;
}
}class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
int maximumProduct = INT_MIN;
int prefix = 1;
int suffix = 1;
for (int i = 0; i < n; i++) {
prefix *= nums[i];
maximumProduct = max(maximumProduct, prefix);
if (nums[i] == 0) {
prefix = 1;
}
}
for (int i = n - 1; i >= 0; i--) {
suffix *= nums[i];
maximumProduct = max(maximumProduct, suffix);
if (nums[i] == 0) {
suffix = 1;
}
}
return maximumProduct;
}
};def max_product(nums: list[int]) -> int:
n = len(nums)
max_prod = float('-inf')
prefix = 1
suffix = 1
for i in range(n):
prefix *= nums[i]
max_prod = max(max_prod, prefix)
if nums[i] == 0:
prefix = 1
for i in range(n - 1, -1, -1):
suffix *= nums[i]
max_prod = max(max_prod, suffix)
if nums[i] == 0:
suffix = 1
return int(max_prod)function maxProduct(nums) {
const n = nums.length;
let maxProduct = -Infinity;
let prefix = 1;
let suffix = 1;
for (let i = 0; i < n; i++) {
prefix *= nums[i];
maxProduct = Math.max(maxProduct, prefix);
if (nums[i] === 0) prefix = 1;
}
for (let i = n - 1; i >= 0; i--) {
suffix *= nums[i];
maxProduct = Math.max(maxProduct, suffix);
if (nums[i] === 0) suffix = 1;
}
return maxProduct;
}Edge Cases to Watch
- Arrays containing zeros (e.g. [2, 3, -2, 4, 0, 7]) which split the problem into independent subarrays
- All negative numbers: odd count vs even count
- Single negative element (e.g. [-2]) — should return -2
- Array with alternating signs and zeros
Algorithmic Pattern
View Pattern Guide →
Master the Dynamic Programming Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Dynamic Programming pattern.
Framework: Dynamic Programming • Interview Prep: Tested at FAANG •
Explore all Dynamic Programming problems & invariants →
How to Recognize This Pattern
- Negative × negative = positive — track min alongside max
- Kadane's variant with two running products
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Tags
Array Dynamic Programming
Frequently Asked Questions
What is the optimal time and space complexity for Maximum Product Subarray?
The optimal solution for Maximum Product Subarray achieves O(n) runtime complexity and requires O(1) auxiliary space. Two linear sweeps (or one combined sweep) of length n require O(n) operations and O(1) auxiliary variables for prefix, suffix, and max product tracking.
How do I identify that Maximum Product Subarray requires the Dynamic Programming pattern?
In technical interviews, look for key problem signals: Negative × negative = positive — track min alongside max; Kadane's variant with two running products. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Dynamic Programming strategy.
What critical edge cases must be handled in Maximum Product Subarray?
Essential edge cases to verify include: Arrays containing zeros (e.g. [2, 3, -2, 4, 0, 7]) which split the problem into independent subarrays; All negative numbers: odd count vs even count; Single negative element (e.g. [-2]) — should return -2; Array with alternating signs and zeros. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Maximum Product Subarray?
Maximum Product Subarray is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Google, Facebook, Microsoft, Bloomberg, Stripe.