algoadvance

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

Clarifying Questions

1. Q: Can the array include negative numbers?
   • A: Yes, the array can include both positive and negative numbers.
2. Q: Can the array have zero values?
   • A: Yes, zero values can be present in the array.
3. Q: What is the range of the length of the array?
   • A: The length of the array can be between 1 and 20000.
4. Q: What is the range of the values of the elements in the array?
   • A: The values of the elements can range from -10 to 10.

Strategy

To solve the problem, we need to iterate through the array while keeping track of three key values during each step:

• max_product which stores the maximum product encountered so far.
• min_product which stores the minimum product encountered so far (important because multiplying two negative numbers can yield a positive product, which might be the maximum product at a later stage).
• result which will store the final maximum product subarray.

The main idea is to update max_product and min_product at each element in the array and compute result as the maximum value of max_product at each step.

Code

def maxProduct(nums):
    if not nums:
        return 0
    
    max_product = min_product = result = nums[0]
    
    for num in nums[1:]:
        if num < 0:
            max_product, min_product = min_product, max_product
        
        max_product = max(num, max_product * num)
        min_product = min(num, min_product * num)
        
        result = max(result, max_product)
    
    return result

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input array nums. This is because we only need to iterate through the array once.

Explanation

1. Initialization: Start with the first element of the array for max_product, min_product, and result.
2. Iteration: For each element in the array (starting from the second element):
   • If the element is negative, swap max_product and min_product because multiplying by a negative number flips the signs.
   • Update max_product to be the maximum of the current element and the product of max_product with the current element.
   • Update min_product to be the minimum of the current element and the product of min_product with the current element.
   • Update result to keep track of the maximum product encountered so far.
3. Return: the maximum product subarray stored in result.

This method ensures that we consider the effects of negative numbers and zeroes efficiently while maintaining a linear time complexity.

Try our interview co-pilot at AlgoAdvance.com

• 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?