LeetCode 152: Maximum Product Subarray Solution in Python Explained
Finding the maximum product of a contiguous subarray might feel like navigating a rollercoaster of numbers with ups, downs, and surprises, and LeetCode 152: Maximum Product Subarray is a medium-level challenge that makes it thrilling! Given an integer array nums
, you need to return the maximum product of any contiguous subarray within it. In this blog, we’ll solve it with Python, exploring two solutions—Dynamic Programming with Min-Max Tracking (our best solution) and Brute Force with All Subarrays (a practical alternative). With step-by-step examples, detailed code breakdowns, and tips, you’ll master this problem. Let’s find that max product!
Problem Statement
In LeetCode 152, you’re given an integer array nums
. Your task is to find the contiguous subarray with the largest product and return that product as an integer. The array may contain positive, negative, and zero values, complicating the product due to sign changes. This differs from string reversal like LeetCode 151: Reverse Words in a String, focusing on array subarray products rather than word manipulation.
Constraints
- 1 <= nums.length <= 2 * 10^4
- -10 <= nums[i] <= 10
- Product fits in a 32-bit integer
Example
Let’s see some cases:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: Subarray [2,3] has max product 6.
<ul>
<li>[2] = 2, [2,3] = 6, [2,3,-2] = -12, [2,3,-2,4] = -48</li>
</ul>
Input: nums = [-2,0,-1]
Output: 0
Explanation: Subarray [0] has max product 0.
<ul>
<li>[-2] = -2, [-2,0] = 0, [0] = 0, [0,-1] = 0, [-1] = -1</li>
</ul>
Input: nums = [-2,3,-4]
Output: 24
Explanation: Subarray [-2,3,-4] has max product 24.
<ul>
<li>[-2] = -2, [-2,3] = -6, [3] = 3, [3,-4] = -12, [-4] = -4</li>
</ul>
These examples show we’re seeking the max product subarray.
Understanding the Problem
How do you solve LeetCode 152: Maximum Product Subarray in Python? Take nums = [2,3,-2,4]
. We need the maximum product—subarray [2,3] gives 6, larger than -48 for the whole array due to negatives. For [-2,0,-1]
, 0 is the max as negatives and zero limit products. This isn’t an expression evaluation like LeetCode 150: Evaluate Reverse Polish Notation; it’s about array subarray optimization. We’ll use:
1. Dynamic Programming with Min-Max Tracking: O(n) time, O(1) space—our best solution.
2. Brute Force with All Subarrays: O(n²) time, O(1) space—an alternative.
Let’s dive into the best solution.
Best Solution: Dynamic Programming with Min-Max Tracking Approach
Explanation
Dynamic Programming with Min-Max Tracking maintains the maximum and minimum products ending at each position, handling sign changes due to negatives. For each number:
- Compute the max and min products including it (considering multiplication by negatives).
- Update the global max product.
- Use only current and previous values, achieving O(1) space.
This is the best solution due to its O(n) time complexity, O(1) space usage, and efficient handling of negative numbers, making it optimal and elegant.
For [2,3,-2,4]
:
- At 2: max=2, min=2.
- At 3: max=6, min=3.
- At -2: max=6, min=-12.
- At 4: max=6, min=-48.
- Result: 6.
Step-by-Step Example
Example 1: nums = [2,3,-2,4]
Goal: Return 6
.
- Start: max_so_far = 2, curr_max = 2, curr_min = 2.
- Step 1: i=1, num=3.
- curr_max = max(3, 2*3, 2*3) = 6.
- curr_min = min(3, 2*3, 2*3) = 3.
- max_so_far = max(2, 6) = 6.
- Step 2: i=2, num=-2.
- curr_max = max(-2, 6*-2, 3*-2) = -2.
- curr_min = min(-2, 6*-2, 3*-2) = -12.
- max_so_far = max(6, -2) = 6.
- Step 3: i=3, num=4.
- curr_max = max(4, -2*4, -12*4) = 4.
- curr_min = min(4, -2*4, -12*4) = -48.
- max_so_far = max(6, 4) = 6.
- Finish: Return 6.
Example 2: nums = [-2,0,-1]
Goal: Return 0
.
- Start: max_so_far = -2, curr_max = -2, curr_min = -2.
- Step 1: i=1, num=0.
- curr_max = max(0, -2*0, -2*0) = 0.
- curr_min = min(0, -2*0, -2*0) = 0.
- max_so_far = max(-2, 0) = 0.
- Step 2: i=2, num=-1.
- curr_max = max(-1, 0*-1, 0*-1) = -1.
- curr_min = min(-1, 0*-1, 0*-1) = -1.
- max_so_far = max(0, -1) = 0.
- Finish: Return 0.
Example 3: nums = [-2,3,-4]
Goal: Return 24
.
- Start: max_so_far = -2, curr_max = -2, curr_min = -2.
- Step 1: i=1, num=3.
- curr_max = max(3, -2*3, -2*3) = 3.
- curr_min = min(3, -2*3, -2*3) = -6.
- max_so_far = max(-2, 3) = 3.
- Step 2: i=2, num=-4.
- curr_max = max(-4, 3*-4, -6*-4) = 24.
- curr_min = min(-4, 3*-4, -6*-4) = -12.
- max_so_far = max(3, 24) = 24.
- Finish: Return 24.
How the Code Works (Dynamic Programming with Min-Max Tracking) – Detailed Line-by-Line Explanation
Here’s the Python code with a thorough breakdown:
def maxProduct(nums: list[int]) -> int:
# Line 1: Handle empty or single-element case
if not nums:
# If nums is empty (not applicable here), return 0
return 0
# Line 2: Initialize variables
max_so_far = nums[0]
# Global max product (e.g., 2)
curr_max = nums[0]
# Max product ending at current (e.g., 2)
curr_min = nums[0]
# Min product ending at current (e.g., 2)
# Line 3: Iterate over array starting from second element
for i in range(1, len(nums)):
# i = current index (e.g., 1 for 3)
num = nums[i]
# Current number (e.g., 3)
# Line 4: Store previous max for min calculation
temp_max = curr_max
# Save current max (e.g., 2)
# Line 5: Update current max
curr_max = max(num, temp_max * num, curr_min * num)
# Max of: num alone, max*num, min*num (e.g., max(3, 2*3, 2*3)=6)
# Handles negatives flipping min to max
# Line 6: Update current min
curr_min = min(num, temp_max * num, curr_min * num)
# Min of: num alone, prev_max*num, prev_min*num (e.g., min(3, 2*3, 2*3)=3)
# Tracks min for negative multiplication
# Line 7: Update global max
max_so_far = max(max_so_far, curr_max)
# e.g., max(2, 6) = 6
# Line 8: Return maximum product
return max_so_far
# Final result (e.g., 6)
This detailed breakdown clarifies how dynamic programming with min-max tracking efficiently finds the maximum product.
Alternative: Brute Force with All Subarrays Approach
Explanation
Brute Force with All Subarrays checks every possible contiguous subarray, computing its product and tracking the maximum. It’s a practical alternative, simple to understand, but O(n²) time makes it less efficient, using O(1) space.
For [2,3,-2,4]
:
- Subarrays: [2], [2,3], [2,3,-2], [2,3,-2,4], [3], [3,-2], etc.
- Max product: 6 from [2,3].
Step-by-Step Example (Alternative)
For [2,3,-2,4]
:
- Step 1: i=0: [2]=2, [2,3]=6, [2,3,-2]=-12, [2,3,-2,4]=-48, max=6.
- Step 2: i=1: [3]=3, [3,-2]=-6, [3,-2,4]=-24, max=6.
- Step 3: i=2: [-2]=-2, [-2,4]=-8, max=6.
- Step 4: i=3: [4]=4, max=6.
- Finish: Return 6.
How the Code Works (Brute Force)
def maxProductBrute(nums: list[int]) -> int:
max_product = nums[0]
for i in range(len(nums)):
curr_product = 1
for j in range(i, len(nums)):
curr_product *= nums[j]
max_product = max(max_product, curr_product)
return max_product
Complexity
- Dynamic Programming with Min-Max Tracking:
- Time: O(n) – single pass.
- Space: O(1) – constant space.
- Brute Force with All Subarrays:
- Time: O(n²) – all subarrays.
- Space: O(1) – constant space.
Efficiency Notes
Dynamic Programming with Min-Max Tracking is the best solution with O(n) time and O(1) space, offering optimal efficiency—Brute Force with All Subarrays uses O(n²) time, making it simpler but slower, though space-efficient.
Key Insights
- Min-Max: Handles negatives.
- DP: Tracks products dynamically.
- Brute: Checks all possibilities.
Additional Example
For nums = [2,-5,-2,-4,3]
:
- Goal: 24.
- DP: Max at -2*3=24 (via min tracking).
Edge Cases
- Single Element: [5] → 5.
- All Negatives: [-1,-2] → 2.
- Zeros: [0,0] → 0.
Both solutions handle these well.
Final Thoughts
LeetCode 152: Maximum Product Subarray in Python is a dynamic array challenge. The Dynamic Programming with Min-Max Tracking solution excels with its efficiency and elegance, while Brute Force with All Subarrays offers a straightforward approach. Want more? Try LeetCode 53: Maximum Subarray for sum version or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 152 on LeetCode with [2,3,-2,4]
, aiming for 6
—test your skills now!