Jobs

Interviews

Discussions

Maximum Product Subarray

Medium

2 views

Topics:

ArraysDynamic Programming

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

The test cases are generated so that the answer will fit in a 32-bit integer.

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⁴
-10 <= nums[i] <= 10
The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

Try coding it in LeetCode

Maximum Product Subarray

Medium

2 views

Topics:

ArraysDynamic Programming

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

The test cases are generated so that the answer will fit in a 32-bit integer.

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⁴
-10 <= nums[i] <= 10
The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array? Could the array contain only negative numbers?
Can the input array `nums` be empty or null?
If the array contains a zero, how should that be handled? Specifically, what should be returned if the entire array's product is zero?
Are we looking for the single maximum product, or the actual subarray itself (e.g., indices)? The prompt asks for "the product", so I want to confirm it's just the product value that needs to be returned.
Is there a minimum size guaranteed for the array, such as at least one element?

Brute Force Solution

Approach

The problem asks us to find the largest product from a continuous section of numbers in a given list. A brute force method involves checking every possible section to find the one with the biggest product.

Here's how the algorithm would work step-by-step:

First, consider the product of just the first number in the list. Store this value.
Then, consider the product of the first two numbers in the list. Store this value and compare it with the value that was previously stored. If this value is larger, replace the stored value with this new value.
Continue this process, considering the product of the first three numbers, the first four numbers, and so on, up to the entire list. Each time, storing the new product, and comparing the new product with the largest product found so far.
Next, start again, this time considering only the second number in the list.
Repeat the same process as before calculating product of the second number, then the second and third, then the second, third, and fourth number and so on, until you have reached the end of the list. Make sure to store and compare the new value with the previously stored largest product.
Do this starting from each number in the list.
After checking the product of every possible section in the list, the largest product you've stored is the answer.

Code Implementation

def max_product_subarray_brute_force(numbers):
    max_product = numbers[0]

    # Iterate through the start indices
    for start_index in range(len(numbers)):
        current_product = 1

        # Iterate through the end indices for each start
        for end_index in range(start_index, len(numbers)):
            current_product *= numbers[end_index]
            # We must keep track of largest product

            if current_product > max_product:
                max_product = current_product

    return max_product

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input array of size n. For each element at index i, it calculates the product of subarrays starting from that index. In the worst case, for each i, it iterates up to n-i elements. Therefore, the total number of operations is proportional to n + (n-1) + (n-2) + ... + 1, which is equivalent to n(n+1)/2. Simplifying this expression, we get O(n²).

Space Complexity

O(1) – The provided solution only stores a single variable to keep track of the maximum product found so far. It doesn't use any auxiliary data structures like arrays, lists, or hash maps that scale with the input size N. Therefore, the amount of extra memory used remains constant regardless of the number of elements in the input list, resulting in a space complexity of O(1).

Optimal Solution

Approach

The key idea is to keep track of the largest and smallest product seen so far as you move through the numbers. This is important because a negative number can turn a small negative into a large positive, and vice versa.

Here's how the algorithm would work step-by-step:

Start by checking each number one by one.
For each number, update what is the biggest product we have seen so far, and what is the smallest product we have seen so far.
The biggest product either comes from multiplying the current number by the previous biggest product, the current number by the previous smallest product, or it is just the current number itself. Pick the biggest one of these three.
The smallest product either comes from multiplying the current number by the previous biggest product, the current number by the previous smallest product, or it is just the current number itself. Pick the smallest one of these three.
Keep track of the overall biggest product you've seen while moving through the numbers.
In the end, the overall biggest product is your answer.

Code Implementation

def max_product_subarray(numbers):
    maximum_product = numbers[0]
    maximum_so_far = numbers[0]
    minimum_so_far = numbers[0]

    for i in range(1, len(numbers)):
        current_number = numbers[i]

        # Need to find max of three possible products.
        temp_max = max(current_number, current_number * maximum_so_far, current_number * minimum_so_far)

        # Need to find min of three possible products.
        minimum_so_far = min(current_number, current_number * maximum_so_far, current_number * minimum_so_far)

        maximum_so_far = temp_max

        # Keep track of overall maximum product.
        maximum_product = max(maximum_product, maximum_so_far)

    return maximum_product

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n once. Inside the loop, it performs a constant number of operations: updating the maximum and minimum products seen so far, and comparing those to update the overall maximum product. Since the work done for each element is constant and we visit each element exactly once, the time complexity is directly proportional to the size of the input, resulting in O(n).

Space Complexity

O(1) – The algorithm described in the plain English explanation uses a fixed number of variables to store the current maximum product, the current minimum product, and the overall maximum product seen so far. The number of these variables does not depend on the size of the input array, denoted as N. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Empty input array	Return 0 or 1, depending on the problem's specification (usually 1 as the product of an empty set is often defined as 1).
Array with a single element	Return that single element as the maximum product subarray.
Array with all zeros	Return 0 as the product of any subarray containing zero will be zero.
Array with all negative numbers	The largest product will be either the single largest element if the array has odd length or the product of all numbers if it has even length.
Array with mixed positive and negative numbers, including zeros	The solution needs to track both the maximum and minimum product ending at each index due to negative number multiplication.
Integer overflow with large numbers	Use a larger data type like long long or consider handling overflows by checking if intermediate products exceed the maximum representable value.
Array contains only the minimum integer value	Handle the potential overflow when multiplying the minimum integer value with itself or another negative number.
Very long input array	The dynamic programming approach ensures linear time complexity, thus scaling well with large input sizes.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array? Could the array contain only negative numbers?
Can the input array `nums` be empty or null?
If the array contains a zero, how should that be handled? Specifically, what should be returned if the entire array's product is zero?
Are we looking for the single maximum product, or the actual subarray itself (e.g., indices)? The prompt asks for "the product", so I want to confirm it's just the product value that needs to be returned.
Is there a minimum size guaranteed for the array, such as at least one element?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, consider the product of just the first number in the list. Store this value.
Then, consider the product of the first two numbers in the list. Store this value and compare it with the value that was previously stored. If this value is larger, replace the stored value with this new value.
Continue this process, considering the product of the first three numbers, the first four numbers, and so on, up to the entire list. Each time, storing the new product, and comparing the new product with the largest product found so far.
Next, start again, this time considering only the second number in the list.
Repeat the same process as before calculating product of the second number, then the second and third, then the second, third, and fourth number and so on, until you have reached the end of the list. Make sure to store and compare the new value with the previously stored largest product.
Do this starting from each number in the list.
After checking the product of every possible section in the list, the largest product you've stored is the answer.

Code Implementation

def max_product_subarray_brute_force(numbers):
    max_product = numbers[0]

    # Iterate through the start indices
    for start_index in range(len(numbers)):
        current_product = 1

        # Iterate through the end indices for each start
        for end_index in range(start_index, len(numbers)):
            current_product *= numbers[end_index]
            # We must keep track of largest product

            if current_product > max_product:
                max_product = current_product

    return max_product

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by checking each number one by one.
For each number, update what is the biggest product we have seen so far, and what is the smallest product we have seen so far.
The biggest product either comes from multiplying the current number by the previous biggest product, the current number by the previous smallest product, or it is just the current number itself. Pick the biggest one of these three.
The smallest product either comes from multiplying the current number by the previous biggest product, the current number by the previous smallest product, or it is just the current number itself. Pick the smallest one of these three.
Keep track of the overall biggest product you've seen while moving through the numbers.
In the end, the overall biggest product is your answer.

Code Implementation

def max_product_subarray(numbers):
    maximum_product = numbers[0]
    maximum_so_far = numbers[0]
    minimum_so_far = numbers[0]

    for i in range(1, len(numbers)):
        current_number = numbers[i]

        # Need to find max of three possible products.
        temp_max = max(current_number, current_number * maximum_so_far, current_number * minimum_so_far)

        # Need to find min of three possible products.
        minimum_so_far = min(current_number, current_number * maximum_so_far, current_number * minimum_so_far)

        maximum_so_far = temp_max

        # Keep track of overall maximum product.
        maximum_product = max(maximum_product, maximum_so_far)

    return maximum_product

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 or 1, depending on the problem's specification (usually 1 as the product of an empty set is often defined as 1).
Array with a single element	Return that single element as the maximum product subarray.
Array with all zeros	Return 0 as the product of any subarray containing zero will be zero.
Array with all negative numbers	The largest product will be either the single largest element if the array has odd length or the product of all numbers if it has even length.
Array with mixed positive and negative numbers, including zeros	The solution needs to track both the maximum and minimum product ending at each index due to negative number multiplication.
Integer overflow with large numbers	Use a larger data type like long long or consider handling overflows by checking if intermediate products exceed the maximum representable value.
Array contains only the minimum integer value	Handle the potential overflow when multiplying the minimum integer value with itself or another negative number.
Very long input array	The dynamic programming approach ensures linear time complexity, thus scaling well with large input sizes.