[Interview Question] How to Solve The Maximum Product Subarray Problem in Python?

[toc]

Company Tags: Amazon, Microsoft

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. It is guaranteed that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

⚠️Constraints:

1. 1 <= nums.length <= 2 * 104
2. -10 <= nums[i] <= 10
3. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Examples

Let us look at some examples to improve our understanding of the problem.

Now that you have a clear understanding of the problem, let’s dive into the methods:

Brute force Method: Linear Traversal

Approach: The idea of this approach is to traverse all the contiguous sub-arrays in the given array and store the product of these arrays. Further, return the maximum product among all the calculated products.

Algorithm:

1. Calculate the length of the array.
2. Initialize a variable “res” and store the initial value as the initial result.
3. Keep traversing the array and updating the “res” variable every time in order to keep track of the maximum product.
4. Finally, update the variable for the (n-1)th index and return it.

Solution:

def max_product(nums):
    n = len(nums)
    res = nums[0]
    for i in range(n):
        prod = nums[i]

        for j in range(i + 1, n):
            res = max(res, prod)
            prod = prod * nums[j]

        res = max(res, prod)

    return res

Test Case Analysis: Let’s run this code on our example.

Hurrah! It passed all the test cases.

Complexity Analysis: As we traversed the array for each sub-array, the time complexity of this method is O(n^2).

Kadane’s Algorithm

Approach: In this approach, you have to keep track of the maximum and minimum product in the array. You have to keep checking whether the element of the array is negative. If yes, then you have to swap the values of the values of minimum and maximum products. Finally, compare these variables to get the maximum product.

Algorithm:

1. Initialize two variables- “max_v” and “min_v” that will store the maximum and minimum product of the array, respectively.
2. Check if the next number in the array is negative. If yes, swap the values of “max_v” and “min_v”
3. After you have completed the traversal, the variables will store the maximum and minimum products.
4. Calculate the maximum product of the array and return it.

Solution:

def max_product(nums):
    n = len(nums)
    min_v = nums[0]
    max_v = nums[0]
    prod = nums[0]

    for i in range(1, n, 1):
        if (nums[i] < 0):
            temp = max_v
            max_v = min_v
            min_v = temp
             
        max_v = max(nums[i], max_v * nums[i])
        min_v = min(nums[i], min_v * nums[i])

        prod = max(prod, max_v)

    return prod

Test Case Analysis: Let’s run this code on our example.

Yeah! It passed all the test cases.

Complexity Analysis: As we traverse the array only once, the time complexity of this method is O(n).

Scanning The Array From Both Ends

Approach: The idea of this approach is to keep track of the maximum product in the given array by traversing it twice, i.e. once from left to right and then from right to left. To traverse the array from the right end to the left end, you can simply reverse the array. You have to traverse each array and keep multiplying every new number derived in each iteration with the value at its previous index. You need to do this for both arrays until you have traversed all the elements. Finally compare all the elements to find the maximum product among them.

Algorithm:

1. Initialize two arrays – “ltor” (stores elements of given array from left to right) and “rtol” (stores elements of given array from right to left).
2. Traverse the array and keep calculating the product of each number with the previous number. Store it in the variables.
3. Calculate the maximum value (product) among both these arrays and return it.

The following diagram illustrates the above mentioned algorithm with the help of an example.

Solution:

def max_product(nums):
    n = len(nums)
    ltor = nums
    rtol = nums[::-1]      
    for i in range(1, n):              
        ltor[i] = ltor[i] * (ltor[i-1] or 1)
        rtol[i] = rtol[i] * (rtol[i-1] or 1)

    return max (max(ltor), max(rtol))

Test Case Analysis: Let’s run this code on our example.

Yeah! It passed all the test cases.

Complexity Analysis: As we traverse the array only once, the time complexity of this method is O(n).

Conclusion

I hope you enjoyed this coding interview question. Please stay tuned and subscribe for more interesting coding problems.

 Post Credits: Shubham Sayon and Rashi Agarwal

Recommended:  Finxter Computer Science Academy

• Do you want to master the most popular Python IDE fast?
• This course will take you from beginner to expert in PyCharm in ~90 minutes.
• For any software developer, it is crucial to master the IDE well, to write, test and debug high-quality code with little effort.