Create account

DEV Community

Rohith V

Posted on Nov 18, 2021 • Edited on Nov 25, 2021

Leetcode 152 : Maximum Product Subarray

#programming #java #algorithms #tutorial

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.

Test Cases :

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

Algorithm :

The most brute force solution is to consider every subarray and take the product keeping track of the maximum product that we have seen so far and finally returning it.
But here the time complexity will be exponential and we can do it better.

Keep two variable prefixProduct and suffixProduct.
Traverse through the array.
Find the prefixProduct. We need to make sure, whenever we see prefixProduct == 0, we need to change it to 1 and continue taking the product because, there can be a chance that maximum product might be somewhere after that. Same procedure with the suffixProduct.

 for (int i=0; i<length; i++) {
            prefixProduct = (prefixProduct == 0 ? 1 : prefixProduct) * nums[i];
            suffixProduct = (suffixProduct == 0 ? 1 : suffixProduct) * nums[length - i - 1];
            result = Math.max(result, Math.max(prefixProduct, suffixProduct));
        }

Always consider the maximum from the maxProduct seen so far and the maximum of prefixProduct and suffixProduct.

Complexity :

The time complexity is O(n) where n = length of array as we only traverse through the array once.
No extra space is being used, so O(1) is space complexity.

Code :

class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        int prefixProduct = 0;
        int suffixProduct = 0;
        int result = nums[0];
        // [2,3,-2,4]
        // 4
        // prefix start from i = 0
        // suffix start from i = 3 = length - i - 1
        for (int i=0; i<length; i++) {
            prefixProduct = (prefixProduct == 0 ? 1 : prefixProduct) * nums[i];
            suffixProduct = (suffixProduct == 0 ? 1 : suffixProduct) * nums[length - i - 1];
            result = Math.max(result, Math.max(prefixProduct, suffixProduct));
        }
        return result;
    }
}