LeetCode 152: Maximum Product Subarray Solution in Python Explained

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!