View on NeetCode
View on LeetCode

Problem

Given an integer array nums, find a subarray that has the largest product, and return the product.

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

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.

Solution

Approach: Track Both Max and Min Products

The key insight is that negative numbers can turn a minimum product into a maximum. We need to track both the maximum and minimum products ending at each position.

Implementation

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if not nums:
            return 0

        max_prod = min_prod = result = nums[0]

        for num in nums[1:]:
            # When we multiply by negative, max becomes min and vice versa
            if num < 0:
                max_prod, min_prod = min_prod, max_prod

            # Update max and min products
            max_prod = max(num, max_prod * num)
            min_prod = min(num, min_prod * num)

            # Update overall result
            result = max(result, max_prod)

        return result

Approach 2: Without Swapping

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if not nums:
            return 0

        max_prod = min_prod = result = nums[0]

        for num in nums[1:]:
            # Store old max_prod before updating
            temp_max = max(num, max_prod * num, min_prod * num)
            min_prod = min(num, max_prod * num, min_prod * num)
            max_prod = temp_max

            result = max(result, max_prod)

        return result

Approach 3: Prefix/Suffix Product

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        result = nums[0]

        # Forward pass
        product = 1
        for num in nums:
            product *= num
            result = max(result, product)
            if product == 0:
                product = 1

        # Backward pass
        product = 1
        for i in range(n - 1, -1, -1):
            product *= nums[i]
            result = max(result, product)
            if product == 0:
                product = 1

        return result

Complexity Analysis

• Time Complexity: O(n), where n is the length of array. Single pass through the array.
• Space Complexity: O(1), only using constant extra space.

Key Insights

1. Negative Numbers Matter: A negative number can turn the minimum product into maximum if we multiply again by negative.

2. Track Both Extremes: We must track both maximum and minimum products because a large negative number times a negative number becomes a large positive.

3. Swap on Negative: When we encounter a negative number, the max and min products swap roles.

4. Reset on Zero: A zero resets the product, so we consider starting a new subarray from the next element.

5. Three Candidates: At each position, the maximum product is either:
   • The current number alone (start new subarray)
   • Current number × previous max product
   • Current number × previous min product (if both negative)
6. Prefix/Suffix Alternative: By considering both forward and backward passes, we handle cases where zeros split the array.