Maximum Product Subarray in O(N) Time – Leetcode Solution

   August 22, 2022
Maximum Product Subarray

Hi everyone! In this post, we are going to discuss a very famous DSA problem known as the Maximum Product Subarray. It is a leetcode medium-level problem. We’ll discuss the problem statement, solution approach, and different methods to solve the problem. In the end, we will see the complete C++ code and Java code for the maximum product subarray.

Table of Contents

  • Maximum product subarray problem statement
  • Problem Explanation
  • Maximum product subarray leetcode solution approach
  • Brute Force Solution of Maximum Product Subarray
  • Pseudo code of O ( N3 ) Approach
  • Pseudo code of O (N2) Approach
  • C++ Solution of Maximum product subarray
  • Java Solution of Maximum product subarray

Maximum Product Subarray Problem Statement

Given an integer array arr, find a non-empty subarray that has the largest product, and return that product. The test cases are generated so that the answer will fit in a 32-bit integer.

Note: A subarray is a contiguous subsequence of the array.

Input

The first line tells the number of test cases. Each test case consists of 2 lines. In the first line of the test case, we have N the number of elements present in the array. In the next line, we have N elements separated by spaces.

Output

Print an integer that tells the maximum product possible by multiplying two or more contiguous elements.

Example

Input: arr = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Input: arr = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Maximum Product Subarray Problem Explanation

The problem is very simple and straightforward. You have to find the maximum product which is possible in the given array by multiplying one or more contiguous elements. The array can have positive integers, negative integers, and zero also. Note this thing that an array can have negative elements and any number of zeroes also. That basically means if you’re considering any sub-array that has one or more zero, its product would be 0 always.

Brute Force Solution of Maximum Product Subarray

The brute force solution is very simple. We can first find out all the sub-arrays of an array and then multiply all elements of the individual subarray and then take the maximum of those. The key idea is to traverse over every possible sub-array, find the product of each of these sub-arrays and return the maximum product from all these results.

If an array has 3 elements then the count of possible non-empty sub-arrays would be 6. An example is given below. Refer to the given image. To find out all the sub-arrays we will need 2 loops and then to multiply all elements we will again traverse all the elements of the subarray. That means O(N3) time complexity. It’s a very naive approach.

Pseudo code of O(N3) Approach

int solve(vector<int> &arr)
{
	int ans = INT_MIN;
	int n = arr.size();
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			int temp = 1;
			for(int k = i; k <= j; k++)
				temp = temp * arr[k];
			
			ans = max(ans, temp);
		}
	}
	return ans;
}
Maximum Product Subarray

We can reduce this O(N3) time complexity to O(N2) easily. We just need to maintain the multiplication of elements while considering the sub-array elements.

int solve(vector<int> &arr)
{
	int ans = INT_MIN;
	int n = arr.size();
	for(int i = 0; i < n; i++)
	{
		int temp = 1;
		for(int j = 0; j < n; j++)
		{
			temp = temp * arr[j];
			ans = max(ans, temp);
		}
	}
	return ans;
}

Maximum Product Subarray O(N) Solution Approach

We can further optimize this to O(N). Now the question arises how? The optimized approach is not very intuitive but it’s really important to learn in order to tackle future problems. So, in the optimized approach, we traverse the array 2 times. One time from left to right (in forwarding direction) and the second time from right to left (in backward direction). Now while traversing we maintain maximum till now and current multiplication. Do not forget to handle the case when the current product becomes zero. You have to reset it to 1. Refer to the below pseudo code.

  1. Declare ans = INT_MIN and curr_prod = 1.
  2. Start loop from i = 0 to n-1 where n is the length of the array.
  3. Update curr_prod as curr_prod = curr_prod * arr[i].
  4. Update ans as ans = max(ans, curr_prod).
  5. Now check if curr_prod is 0, and reset it to 1.
  6. End loop.
  7. Update curr_prod as curr_prod = 1.
  8. Run loop from i = n -1 to 0.
  9. Update curr_prod as curr_prod = curr_prod * arr[i].
  10. Update ans as ans = max(ans, curr_prod).
  11. Now check if curr_prod is 0, and reset it to 1.
  12. End loop.
  13. Return ans.

Note: The claim is maximum product will lie from index 0 to k OR from index k to n-1.

The whole solution is based on the above claim. It’s an observation. You can verify this using some examples on your own. The time complexity of this solution would be O(N) since we’re just using 2 loops to traverse the given array in both directions. The space complexity would be O(1) since we are just using some variables and not using any auxiliary space.

C++ Solution of Maximum product subarray 

int solve(vector<int>& arr) 
{
    int n = arr.size();
    if(n == 1) 
        return arr[0];

    long long ans = INT_MIN;
    long long curr_prod = 1;
	    
    for(int i = 0; i < n; i++)
    {
        curr_prod = curr_prod * arr[i];
	ans = max(curr_prod, ans);
	if(curr_prod == 0)
	     curr_prod = 1;
    }

    curr_prod = 1;

    for(int i = n-1; i >= 0; i--)
    {
	curr_prod = curr_prod * arr[i];
	ans = max(curr_prod, ans);
	if(curr_prod == 0)
	   curr_prod = 1;
     }
	    
     return ans;
}

Time Complexity: O ( 2 * N ) => O ( N )

Space Complexity: O ( 1 )

Java Solution of Maximum product subarray 


int solve(int[] nums) 
{ 
        
    int ans = Integer.MIN_VALUE, curr_prod = 1;     
    
    for(int i = 0; i < nums.length; i++) {
    	curr_prod = curr_prod * nums[i];
        ans = Math.max(ans, curr_prod);
        if(curr_prod == 0) 
        	curr_prod = 1;
    }
        
    curr_prod = 1;
	for(int i = nums.length-1; i>=0; i--)
	{
        curr_prod = curr_prod * nums[i];
        ans = Math.max(ans, curr_prod);
        if(curr_prod == 0) 
        	curr_prod = 1;
	}
        
    return ans;
}

Time Complexity: O ( 2 * N ) => O ( N )

Space Complexity: O ( 1 )

If you’re preparing for product-based companies, you should definitely check out these Top 20 Array Coding Questions for Online Assessment.

If you want us to add more coding questions kindly tell us in the comments. Don’t forget to share it with your friends. Thanks 🙂

Also Read:

Share:

Author: Ayush Purawr