Hashing — Maximum Product Subarray
↗ LeetCode: Maximum Product Subarray · Medium · pattern chapter →
Asked atMetaAmazonLinkedIn
Return max product of a contiguous subarray.
Example 1 — nums=[2,3,-2,4] → 6Example 2 — nums=[-2,0,-1] → 0
Constraints — 1 ≤ n ≤ 2·10⁴. Brute enumerates every subarray — O(n²) = 4·10⁸ ops at n=2·10⁴ (TLE past ~5 sec). DP tracking min+max at each index (product sign can flip) is O(n) = 2·10⁴ ops.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
⏱️Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Try every subarray
O(n²). Baseline.
Approach 2 — Track min and max ending at i (canonical)
Insight. A negative flips min ↔ max on the next step. Maintain both.
java
int maxProduct(int[] nums) {
int maxE = nums[0], minE = nums[0], best = nums[0];
for (int i = 1; i < nums.length; i++) {
int x = nums[i];
int nMax = Math.max(x, Math.max(maxE * x, minE * x));
int nMin = Math.min(x, Math.min(maxE * x, minE * x));
maxE = nMax; minE = nMin;
best = Math.max(best, maxE);
}
return best;
}1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
Execution Trace
Complexity — Time O(n); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| All subarrays | O(n²) | O(1) | baseline |
| Min/Max tracking | O(n) | O(1) | canonical |
When to use which
- "Product with negatives" → track both.
- "Only positives" → simple running product.
- "Return the subarray" → track indices.
✨AI Study CompanionBeta
Related problems
Was this page helpful?