Log inSign up
mediumLeetCodeNot Started

Maximum Product Subarray

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return *the product*.

The test cases are generated so that the answer will fit in a 32-bit integer.

---

### Constraints: - 1 <= nums.length <= 2 * 10^4 - -10 <= nums[i] <= 10 - The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Example 1 · Example 1 (Positive Subarray Window):

Input: nums = [2, 3, -2, 4]
Output: 6
Explanation: The contiguous subarray [2, 3] yields the maximum product 2 * 3 = 6.

Example 2 · Example 2 (Zero Separator):

Input: nums = [-2, 0, -1]
Output: 0
Explanation: Subarrays [-2] gives -2, [0] gives 0, and [-1] gives -1. The maximum contiguous product is 0.

Example 3 · Example 3 (Two Negatives Multiplying to Positive):

Input: nums = [-2, 3, -4]
Output: 24
Explanation: The entire array [-2, 3, -4] multiplies to (-2) * 3 * (-4) = 24.

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Array Indexing
  • Basic Time & Space Complexity Analysis

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why standard Kadane's algorithm fails for products due to sign inversion.
  • Master simultaneous maximum and minimum state tracking.
  • Handle zero values as dynamic partition boundaries.
  • Implement clean, standalone solutions across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Contiguous subarray optimization involving multiplication / products.
  • Array contains negative numbers and zeroes.
  • Sign-flipping property of multiplication.

Algorithmic Decision Tree:

  • For Maximum Subarray Sum: Standard Kadane (only track max).
  • For Maximum Subarray Product: Dual Kadane (track both max and min).

Connected Patterns:

Maximum Subarray (Kadane's algorithm): Maximum sum.Subarray Product Less Than K: Sliding window for positive numbers.Maximum Length of Subarray With Positive Product: Tracking positive/negative lengths.

1. Nested Loops All Subarrays

Intuition

Compute the product of every possible subarray (i..j) and record the maximum product.

Algorithm

  1. 1. Initialize maxProd = nums[0].
  2. 2. For i from 0 to n-1: - currentProd = 1 - For j from i to n-1: - currentProd *= nums[j] - maxProd = max(maxProd, currentProd).
  3. 3. Return maxProd.

Brute Force All Subarrays Product Scan

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [2, 3, -2, 4, -1]
Current operationSTEP 1 OF 7
Phase 1 — maxProd = 2: Step 1: Fix start index i=0
Visual state
Values and pointers at this exact step
array
S
2
3
-2
4
-1
0
↑ i=0 (val 2)
1
2
3
4
Variables at this step
i
0
j
0
Product
2
maxProd
2
Check / comparison
Start subarray at i=0. Subarray [2]: product = 2.
Decision / next transition
maxProd = 2.
Why this step matters

Phase 1 — maxProd = 2: Step 1: Fix start index i=0. Single-element subarray [2] product is 2. Initialize maxProd = 2.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 int maxProduct(vector<int>& nums) {
17 int n = nums.size();
18 int maxProd = nums[0];
19 for (int i = 0; i < n; ++i) {
20 int prod = 1;
21 for (int j = i; j < n; ++j) {
22 prod *= nums[j];
23 maxProd = max(maxProd, prod);
24 }
25 }
26 return maxProd;
27 }
28};
29
30int main() {
31 Solution sol;
32 vector<int> nums = {2, 3, -2, 4};
33 cout << "Maximum Product Subarray: " << sol.maxProduct(nums) << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N^2) — Two nested loops check all N*(N+1)/2 subarrays in O(N2) time.
  • Space complexity: O(1) — Auxiliary space is O(1).

Why Brute Force Doesn't Scale:

At any index i, the best product ending at i only depends on three choices: start fresh with nums[i], extend the previous max product (nums[i] * max_prod), or extend the previous min product (nums[i] * min_prod). By maintaining these two values in scalar registers, we solve the problem in a single pass of N steps.

For N = 20,000: Brute Force takes ~200,000,000 operations (~1s). Dual Kadane takes ~20,000 ops (< 1ms).

2. Prefix and Suffix Running Product Scan

Intuition

Scan from left-to-right and right-to-left simultaneously; reset product to 1 on zero.

Algorithm

  1. 1. Initialize prefix = 1, suffix = 1, maxProd = -infinity.
  2. 2. For i from 0 to n-1: - If prefix == 0, prefix = 1 - If suffix == 0, suffix = 1 - prefix *= nums[i] - suffix *= nums[n - 1 - i] - maxProd = max(maxProd, max(prefix, suffix)).
  3. 3. Return maxProd.

Prefix & Suffix Product Scanning

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 3, -2, 4, -1]
Current operationSTEP 1 OF 6
Phase 1 — maxProd = max(2, -1) = 2: Step 1: Run two simultaneous accumulators: prefix from left, suffix from right
Visual state
Values and pointers at this exact step
array
S
2
3
-2
4
-1
0
↑ Pref idx 0 (val 2)
1
2
3
4
↑ Suff idx 4 (val -1)
Variables at this step
pref
2
suff
-1
maxProd
2
Check / comparison
pref = 1 * nums[0] = 2. suff = 1 * nums[4] = -1.
Decision / next transition
maxProd = max(2, -1) = 2.
Why this step matters

Phase 1 — maxProd = max(2, -1) = 2: Step 1: Run two simultaneous accumulators: prefix from left, suffix from right. Left pref = 2, right suff = -1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 int maxProduct(vector<int>& nums) {
17 int n = nums.size();
18 double prefix = 1, suffix = 1;
19 double maxProd = INT_MIN;
20 for (int i = 0; i < n; ++i) {
21 if (prefix == 0) prefix = 1;
22 if (suffix == 0) suffix = 1;
23 prefix *= nums[i];
24 suffix *= nums[n - 1 - i];
25 maxProd = max({maxProd, prefix, suffix});
26 }
27 return (int)maxProd;
28 }
29};
30
31int main() {
32 Solution sol;
33 vector<int> nums = {2, 3, -2, 4};
34 cout << "Maximum Product Subarray: " << sol.maxProduct(nums) << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N) — A single traversal of size N computes both prefix and suffix products in O(N) time.
  • Space complexity: O(1) — Uses only scalar accumulator variables, requiring O(1) space.

3. Dynamic Programming / Kadane Variant (Track Min & Max)

Intuition

Maintain both maxProd and minProd at each position; when multiplied by a negative number, min and max swap roles.

Algorithm

  1. 1. Initialize maxSoFar = nums[0], minSoFar = nums[0], result = nums[0].
  2. 2. For i from 1 to n-1: - If nums[i] < 0, swap(maxSoFar, minSoFar) - maxSoFar = max(nums[i], maxSoFar * nums[i]) - minSoFar = min(nums[i], minSoFar * nums[i]) - result = max(result, maxSoFar).
  3. 3. Return result.

Kadane's Dynamic Variant (Min/Max Negative Swapping)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 3, -2, 4, -1]
Current operationSTEP 1 OF 6
Phase 1 — Base state established: Step 1 (Idx 0): We track both curMax and curMin because multiplying by a negative will flip them
Visual state
Values and pointers at this exact step
array
S
2
3
-2
4
-1
0
↑ i=0 (val 2)
1
2
3
4
Variables at this step
curMax
2
curMin
2
maxResult
2
Check / comparison
Initialize curMax = nums[0] (2), curMin = nums[0] (2), maxResult = 2.
Decision / next transition
Base state established.
Why this step matters

Phase 1 — Base state established: Step 1 (Idx 0): We track both curMax and curMin because multiplying by a negative will flip them! Initial: curMax = 2, curMin = 2, maxResult = 2.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 int maxProduct(vector<int>& nums) {
17 int maxSoFar = nums[0];
18 int minSoFar = nums[0];
19 int result = nums[0];
20
21 for (size_t i = 1; i < nums.size(); ++i) {
22 int curr = nums[i];
23 if (curr < 0) swap(maxSoFar, minSoFar);
24
25 maxSoFar = max(curr, maxSoFar * curr);
26 minSoFar = min(curr, minSoFar * curr);
27
28 result = max(result, maxSoFar);
29 }
30 return result;
31 }
32};
33
34int main() {
35 Solution sol;
36 vector<int> nums = {2, 3, -2, 4};
37 cout << "Maximum Product Subarray: " << sol.maxProduct(nums) << endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N) — Single linear pass through the array performing O(1) operations per element.
  • Space complexity: O(1) — Uses only 3 scalar variables (maxSoFar, minSoFar, result). Space is O(1).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.1. All Subarrays (Brute Force)O(N^2)O(1)Compute product for every subarray starting at i and ending at j.Recomputes product of all N2 / 2 subarrays.
2.2. Prefix & Suffix Product Scan (Better)O(N)O(1)Scan array left-to-right (prefix) and right-to-left (suffix), resetting product to 1 at zero.Two accumulator passes.
3.3. Kadane's Dual Min/Max State (Optimal)OptimalO(N)O(1) auxiliarySingle pass maintaining max_prod and min_prod with swap on negative values.Optimal linear runtime and space.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Single element array (e.g. [-5]): Returns that single element directly.
  • Array containing zeroes (e.g. [-2, 0, -1]): Zero resets product, handled cleanly by Math.max(x, ...).
  • All negative numbers: Correctly pairs adjacent negatives or returns the largest single negative element.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for undefined?

2.Why is the brute force approach suboptimal for large inputs in undefined?

3.Which data structure or technique enables the optimal solution for undefined?

Back to DSA Sheet