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
andsuffixProduct
. - Traverse through the array.
- Find the
prefixProduct
. We need to make sure, whenever we seeprefixProduct == 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 thesuffixProduct
.
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;
}
}
Github :
Rohithv07 / LeetCodeTopInterviewQuestions
Leetcode Top Interview questions discussed in Leetcode. https://leetcode.com/explore/interview/card/top-interview-questions
LeetCodeTopInterviewQuestions
Leetcode Top Interview questions discussed in Leetcode. https://leetcode.com/explore/interview/card/top-interview-questions-easy/
Also Question answered from CodeSignal.com : https://app.codesignal.com/
Top comments (0)