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 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.

Clarifying Questions

1. Q: What should be returned if the array is empty?
   • A: The problem specifies that the input array is non-empty.
2. Q: Can the array contain both positive and negative numbers?
   • A: Yes, the array can contain positive, negative, and zero values.
3. Q: What will be the size range of the input array?
   • A: The size of the input array is typically constrained by the problem specifications; we will assume it to be reasonable for typical integer array problems (e.g., 1 <= nums.length <= 2 * 10^4).

Strategy

1. Dynamic Programming Approach:
   • We need to keep track of both the maximum and minimum product subarray ending at the current position since a minimum product (negative value) multiplied by a negative number could become a maximum product.
   • Use two variables to maintain the maximum and minimum products ending at the current index.
   • Iterate through the array, updating these two variables accordingly.
   • Update the result whenever the maximum product variable is updated.

Code

public class Solution {
    public int maxProduct(int[] nums) {
        // Edge case: Empty array is not allowed as per problem statement
        if(nums.length == 0) return 0;
        
        // Initialize the variables for tracking maximum and minimum products
        int maxProduct = nums[0];
        int minProduct = nums[0];
        int result = nums[0];
        
        // Iterate through the array starting from index 1
        for(int i = 1; i < nums.length; i++) {
            // If the current number is negative, swap the max and min products
            if(nums[i] < 0){
                int temp = maxProduct;
                maxProduct = minProduct;
                minProduct = temp;
            }
            
            // Update the maximum and minimum products ending at the current position
            maxProduct = Math.max(nums[i], maxProduct * nums[i]);
            minProduct = Math.min(nums[i], minProduct * nums[i]);
            
            // Update the result with the maximum found so far
            result = Math.max(result, maxProduct);
        }
        
        return result;
    }
}

Time Complexity

• Time Complexity: O(n) where n is the number of elements in the input array. We go through the array once.
• Space Complexity: O(1). We use a constant amount of extra space. The variables maxProduct, minProduct, and result are used to keep track of the required values.

This approach ensures that we efficiently find the maximum product of a contiguous subarray while keeping the implementation straightforward.

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?