Maximum Product Subarray
Asked at Google, Meta, Amazon, Microsoft, Apple, Uber, Walmart
Problem
Given an integer array nums, find a contiguous non-empty subarray that has the largest product, and return the product. The answer is guaranteed to fit in a 32-bit integer.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Apple | Medium | View all Apple questions → |
| Uber | Medium | View all Uber questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Unlike maximum sum, products can flip sign. A negative times a negative becomes positive. So the minimum product at position i-1 can become the maximum at position i.
Track both maxProd and minProd at each position. When nums[i] is negative, swap them (the max becomes min and vice versa).
At each element, the candidates are: the element itself (start fresh), maxProd × element (extend max), minProd × element (extend min, might flip to positive).
Why it works: by tracking both max and min, you handle the sign-flip property of multiplication.
Visual walkthrough for [2,3,-2,4]:
num=2: maxProd=2, minProd=2, result=2
num=3: maxProd=max(3,2×3)=6, minProd=min(3,2×3)=2, result=6
num=-2: swap → maxProd=2, minProd=6. maxProd=max(-2,2×(-2))=-2, minProd=min(-2,6×(-2))=-12, result=6
num=4: maxProd=max(-4,-12×4)=max(-4,-48)=-2? No: maxProd=4 (start fresh), minProd=-48. result=6.
Wait: maxProd=max(4, -2×4, -12×4)=max(4,-8,-48)=4. result=max(6,4)=6.
Result: 6 (subarray [2,3]).
Edge cases: single element (return it), all negatives (pair them), zeros (reset).
Optimal Approach
Step 1: Initialize maxProd = minProd = result = nums[0].
Step 2: For each num in nums[1:]:
If num < 0, swap maxProd and minProd.
maxProd = max(num, maxProd × num)
minProd = min(num, minProd × num)
result = max(result, maxProd)
Step 3: Return result.
Time: O(n). Space: O(1).
What Trips People Up in Real Interviews
Confusing this with maximum sum subarray. Products can flip sign — a negative times a negative becomes positive. You need to track both max and min.
Not tracking the minimum product. The minimum product at position i-1 can become the maximum at position i if nums[i] is negative.
Forgetting to swap max and min when nums[i] is negative. This handles the sign flip.
Not handling zeros. A zero resets both max and min to the current element.
Forgetting to initialize result with nums[0] instead of 0. If all products are negative, 0 would be wrong — the answer is the least negative single element.
Solution Code
def maxProduct(nums):
result = max_prod = min_prod = nums[0]
for num in nums[1:]:
if num < 0:
max_prod, min_prod = min_prod, max_prod
max_prod = max(num, max_prod * num)
min_prod = min(num, min_prod * num)
result = max(result, max_prod)
return resultFrequently Asked Questions
What is the Maximum Product Subarray problem?
Given an integer array nums, find a contiguous non-empty subarray that has the largest product, and return the product. The answer is guaranteed to fit in a 32-bit integer.
How do you solve Maximum Product Subarray?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Maximum Product Subarray?
Maximum Product Subarray is asked at Google, Meta, Amazon, Microsoft, Apple, Uber, Walmart. It is a medium difficulty problem.
What are common mistakes on Maximum Product Subarray?
- Confusing this with maximum sum subarray. Products can flip sign — a negative times a negative becomes positive. You need to track both max and min.
- Not tracking the minimum product. The minimum product at position i-1 can become the maximum at position i if `nums[i]` is negative.
- Forgetting to swap max and min when `nums[i]` is negative. This handles the sign flip.
- Not handling zeros. A zero resets both max and min to the current element.
- Forgetting to initialize result with `nums[0]` instead of 0. If all products are negative, 0 would be wrong — the answer is the least negative single element.