A LeetCode Daily Series — Day 61

In this article, we will explore the problem of finding the maximum product subarray in a given integer array. We will dive into the problem, understand the constraints, and then look at both brute force and efficient approaches to solve it.

Maximum Product Subarray - LeetCode leetcode.com

Can you solve this real interview question? Maximum Product Subarray

If you’re just joining us, it might be helpful to catch up on the previous entries. Want to see more problem-solving techniques? Follow me here on my blog!

A LeetCode Daily Series — Introduction | Ritesh Shakya riteshakya.com.np

Hey everyone, I’m excited to announce that I’m embarking on a journey to conquer LeetCode!

Understanding the Problem

The problem at hand requires us to find a subarray within a given integer array that has the largest product and return that product. The challenge includes handling both positive and negative numbers, as well as zeros, which can significantly affect the product calculations.

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.

Brute Force Approach

The brute force approach involves considering all possible subarrays and calculating their products to find the maximum product. While this approach is straightforward, it can be very slow for large arrays due to its high time complexity.

def maxProduct(self, nums: List[int]) -> int:
    max_product = float('-inf')

    for i in range(len(nums)):
        current_product = 1
        for j in range(i, len(nums)):
            current_product *= nums[j]
            max_product = max(max_product, current_product)

    return max_product

Explanation

1. Initialization: The max_product variable is initialized to negative infinity to ensure any product calculated will be larger.
2. Nested Loops: The outer loop starts at each index of the array. The inner loop calculates the product of subarrays starting from the outer loop index.
3. Product Calculation: For each subarray, the product is calculated and updated in the max_product if it is larger than the current max_product.
4. Return: Finally, return the max_product.

Time Complexity: O(n^2), where 𝑛 is the length of the input array. We are considering all subarrays and their products.

Space Complexity: O(1). We use a constant amount of extra space regardless of the input size.

Using Efficient Approach (Dynamic Programming)

The dynamic programming approach involves maintaining two variables, curMax and curMin, which represent the maximum and minimum products ending at the current position. This approach allows us to handle the presence of negative numbers and zeros effectively.

def maxProduct(self, nums: List[int]) -> int:
    res = max(nums)

    curMin, curMax = 1, 1

    for n in nums:
        tempMax = curMax * n
        tempMin = curMin * n
        curMax = max(tempMax, tempMin, n)
        curMin = min(tempMax, tempMin, n)
        res = max(curMax, res)

    return res

Explanation

1. Initialization: The result (res) is initialized to the maximum value in the array to account for the case when the array contains only one element.
2. Current Minimum and Maximum: curMin and curMax are initialized to 1, representing the initial product values.
3. Iteration: We iterate through each number in the array. For each number:

• Calculate tempMax and tempMin as the product of the current number with curMax and curMin, respectively.
• Update curMax to be the maximum of tempMax, tempMin, and the current number. This handles the case where the current number itself might be larger than any product we have seen so far.
• Update curMin similarly to handle the smallest product.
• Update the result (res) to be the maximum of curMax and the current result.

4. Return: Finally, return the result.

Time Complexity: O(n), where 𝑛 is the length of the input array. We only traverse the array once.

Space Complexity: O(1). We use a constant amount of extra space regardless of the input size.

Conclusion

Finding the maximum product subarray is a classic problem that can be solved in multiple ways. The brute force approach, though simple, is not efficient for large arrays. The dynamic programming approach provides an optimal solution with linear time complexity, making it suitable for large inputs. By maintaining running maximum and minimum products, we can handle the complexity introduced by negative numbers and zeros effectively.

Each approach has its trade-offs in terms of time and space complexity, and choosing the right approach depends on the constraints of the problem and the size of the input.

Found this helpful? Follow me for more leetcode adventures! Questions? React out via email.

Next Articles in the Series

A LeetCode Daily Series — Day 62 | Ritesh Shakya riteshakya.com.np

Today’s problem is called “Longest Increasing Subsequence”