DEV Community

Cover image for Leetcode 152 : Maximum Product Subarray
Rohith V
Rohith V

Posted on • Updated on

Leetcode 152 : Maximum Product Subarray

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.

  1. Keep two variable prefixProduct and suffixProduct.
  2. Traverse through the array.
  3. 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));
        }
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Github :

GitHub logo Rohithv07 / LeetCode

LeetCode problems that are solved.

LeetCode

LeetCode problems that are solved.

  • take the bit of the ith(from right) digit:

    bit = (mask >> i) & 1;

  • set the ith digit to 1: mask = mask | (1 << i);

  • set the ith digit to 0: mask = mask & (~(1 << i));

A Sample Structure




GitHub logo Rohithv07 / LeetCodeTopInterviewQuestions

Leetcode Top Interview questions discussed in Leetcode. https://leetcode.com/explore/interview/card/top-interview-questions




Top comments (0)