algoadvance

Leetcode 152. Maximum Product Subarray

Problem Statement

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

Example:

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

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.

Clarifying Questions

1. Q: Can the array contain zeros, and how should they be handled? A: Yes, the array can contain zeros. Subarrays consisting of zeros should be considered, and we need to reset our current product calculations when encountering a zero.

2. Q: Are there any constraints on the product value range? A: No, but the constraints ensure that any product will fit within a 32-bit integer bound.

3. Q: Should we handle larger optimizations, like a divide-and-conquer approach? A: While divide-and-conquer is an interesting approach, the problem can be efficiently solved using a linear scan with dynamic programming principles.

Strategy

The main idea is to keep track of the maximum and minimum product subarray ending at each position, because a new number multiplied by a minimum product can potentially become the maximum product (e.g., negative number multiplied by a negative minimum product).

1. Initialize three variables:
   • max_product to store the final max product found so far.
   • current_max to store the current maximum product up to the current index.
   • current_min to store the current minimum product up to the current index (to handle cases where a negative number can turn a small minimum product into a large maximum product).
2. Iterate through the array, and for each element:
   • Compute new potential max and min values by considering the current element itself, the product of the current max with this element, and the product of the current min with this element.
   • Update the current max and min accordingly.
   • Update the overall max_product.

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxProduct(std::vector<int>& nums) {
        if(nums.empty()) return 0; // Edge case, although constraints say nums is non-empty

        int max_product = nums[0];
        int current_max = nums[0];
        int current_min = nums[0];

        for(size_t i = 1; i < nums.size(); ++i) {
            int num = nums[i];
            if (num < 0) {
                std::swap(current_max, current_min);
            }
            current_max = std::max(num, current_max * num);
            current_min = std::min(num, current_min * num);
            max_product = std::max(max_product, current_max);
        }

        return max_product;
    }
};

Time Complexity

• Time Complexity: O(n) - Where n is the length of the input array. We traverse the array once.
• Space Complexity: O(1) - Only a fixed amount of extra space is used.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?