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

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.

Example 1:
Input: nums = [2, 3, -2, 4]
Output: 6
Explanation: The sub-array [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 sub-array.

Example 3:
Input: nums = [6, -3, -10, 0, 2]
Output: 180
Explanation: The sub-array [6, -3, -10] has the largest product, 180.

Example 4:
Input: nums = [-2, -3, 0, -2, -40]
Output: 80
Explanation: The sub-array [-2, -40] has the largest product, 80.

Example 5:
Input: nums = [10, 20]
Output: 200
Explanation: The sub-array [10, 20] has the largest product, 200.

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

Brute force Method: Linear Traversal

Approach: The basic idea of this approach is to traverse all the contiguous sub-arrays in the array list and store the product of these arrays. Further, return the max product among these.

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.

# Example 1
nums = [2, 3, -2, 4]
print(max_product(nums))
# 6

# Example 2
nums = [-2, 0, -1]
print(max_product(nums))
# 0

# Example 3
nums = [6, -3, -10, 0, 2]
print(max_product(nums))
# 180

# Example 4
nums = [-2, -3, 0, -2, -40]
print(max_product(nums))
# 80

# Example 5
nums = [10, 20]
print(max_product(nums))
# 200

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

[Optimal Solution]: Kadane’s Algorithm

Approach: In this approach, you have to keep track of the maximum and minimum product in the array. Keep checking whether the element of the array is negative. If yes, then the values of minimum and maximum products get swapped. Then 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.

# Example 1
nums = [2, 3, -2, 4]
print(max_product(nums))
# 6

# Example 2
nums = [-2, 0, -1]
print(max_product(nums))
# 0

# Example 3
nums = [6, -3, -10, 0, 2]
print(max_product(nums))
# 180

# Example 4
nums = [-2, -3, 0, -2, -40]
print(max_product(nums))
# 80

# Example 5
nums = [10, 20]
print(max_product(nums))
# 200

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

[Alternate Approach]: Scanning Twice

Approach: The idea of this approach is to keep track of the maximum product in the array two times- from left to right and from right to left. You have to multiply each new number on both sides and compare to find the maximum product.

Algorithm:

  1. Initialize two variables- “ltor” (left to right) and “rtol” (right to left) at the start and end of the array.
  2. Traverse the array and keep calculating the product of each number with the previous number. Store it in the variables.
  3. Calculate the max product in both these arrays and return the max product among those two.

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.

# Example 1
nums = [2, 3, -2, 4]
print(max_product(nums))
# 6

# Example 2
nums = [-2, 0, -1]
print(max_product(nums))
# 0

# Example 3
nums = [6, -3, -10, 0, 2]
print(max_product(nums))
# 180

# Example 4
nums = [-2, -3, 0, -2, -40]
print(max_product(nums))
# 80

# Example 5
nums = [10, 20]
print(max_product(nums))
# 200

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.
The Complete Guide to PyCharm
Join the PyCharm Masterclass now, and master PyCharm by tomorrow!