Problem Statement
Given an integer array nums. Find the subarray with the largest product, and return the product of the elements present in that subarray.
A subarray is a contiguous non-empty sequence of elements within an array.
LeetCode:
Constraints:
1 <= nums.length <= 2 * 10^4
-10 <= nums[i] <= 101 ≤ nums.length ≤ 2 * 10^4- The input array
numshas at least 1 element. - It can have up to 20,000 elements.
- You algo needs to be efficient, ideally
O(n log n). - Native brute force solutions (like
O(n^2)might work for small inputs but will time out for large arrays.
- The input array
-10 ≤ nums[i] ≤ 10- Each element in the array is very small in value.
- The range of possible values if from -10 to +10 (inclusive), i.e., just 21 unique values.
Examples
Example 1:
Input: nums = [4, 5, 3, 7, 1, 2]
Output: 840
Explanation: The largest product is given by the whole array itself.Example 2:
Input; nums = [-5, 0, -2]
Output: 0
Explanation: The largest product is achieved with the following subarrays [0], [-5, 0], [0, -2], [-5, 0, -2]Different Approaches
1️⃣ Brute Force Approach
Intuition:
The naive way is to identify all possible subarrays using nested loops. For each subarray, calculate the product of its elements. Ultimately, return the maximum product found among all subarrays.
Approach:
- Iterate in the array using i which runs from 0 to sizeOfArray - 1, it will basically identify the starting point of the subarrays.
- Now run an inner loop using j from i+1 to sizeOfArray - 1, it will identify the ending point of the subarrays. Inside this loop, iterate again from i to j and multiply elements present in the chosen range.
- Update the maximum product after each iteration and finally, return it.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to find maximum product subarray
int maxProduct(vector<int>& nums) {
// Initialize result to minimum possible integer
int result = INT_MIN;
// Iterate through all subarrays
for (int i = 0; i < nums.size(); i++) {
for (int j = i; j < nums.size(); j++) {
int prod = 1;
// Calculate product of subarray
for (int k = i; k <= j; k++) {
prod *= nums[k];
}
// Update the result with maximum product found
result = max(result, prod);
}
}
// Return the maximum product found
return result;
}
};
int main() {
vector<int> nums = {4, 5, 3, 7, 1, 2};
// Create an instance of the Solution class
Solution sol;
int maxProd = sol.maxProduct(nums);
// Print the result
cout << "The maximum product subarray: " << maxProd << endl;
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N^3)for using 3 nested loops for finding all possible subarrays and their product. Here N is the size of the array. - Space Complexity:
O(1), as no additional space is used apart from the input array.
2️⃣ Better Approach
Intuition:
A better idea is to maximize the product using two loops. In the innermost loop of the brute-force solution, observe that we calculate the product of subarrays starting from index i to j. However, it can be optimized by computing the product incrementally. Multiplying arr[j] in the second loop with the previous product. This approach improves the time complexity of the solution.
Approach:
- Iterate in the array using i which starts from 0 and goes till sizeOfArray - 1. Now, iterate in array using an inner loop using j, which starts from i+1 and goes till sizeOfArray - 1. Initialize a variable prod to store product and max to store maximum product.
- Inside this loop, multiply arr[j] to prod variable in each iteration and update the max variable each time. Finally, return max variable as an answer.
Code:
class Solution {
public:
int maxProduct(vector<int>& nums) {
int maxProduct = INT_MIN;
for (int i = 0; i < nums.size(); i++) {
int product = 1;
for (int j = i; j < nums.size(); j++) {
product *= nums[j];
maxProduct = max(maxProduct, product);
}
}
return maxProduct;
}
};Complexity Analysis:
- Time Complexity:
O(N^2)for using 2 nested loops for finding all possible subarrays and their product. Here N is the size of the array. - Space Complexity:
O(1)as no additional space is used apart from the input array.
3️⃣ Optimal Approach
Intuition:
The goal is to find the subarray having the maximum product of elements. To solve the problem efficiently, we need to understand the following points:
- The product of an even number of negative numbers result in a positive product, whereas the product of an odd number of negative numbers result in a negative product.
- If an array element is zero, considering it in the subarray will result in product as 0, giving the idea of skipping it.
The multiplication of all the elements in the array could have been our answer if there were all positives or even negatives in the array (with no element as 0) but the problem arises when there are odd number of negative elements in the array.
Understanding:
When the array has an odd number of negative elements, one must be excluded to make their product positive. Since the subarray must be contiguous, only the first or last negative element can be removed. By calculating the product from both directions — prefix and suffix — we can determine the maximum product subarray.
When there are zeroes in the array?
When there are zeroes in the array, the prefix and suffix will end up becoming zero. Hence, whenever the prefix or the suffix are found to be zero, it means that a zero element was found meaning that we must reassign them with the value 1.
Note that the two-directional traversal (prefix and suffix) is achieved within a single loop, avoiding the need for separate iterations. This makes the solution more efficient while maintaining simplicity.
Approach:
- Initialize a variable to store the maximum product result.
- Maintain two running products: one for the prefix (left to right traversal) and one for the suffix (right to left traversal).
- Iterate through the array:
- If the running product becomes zero, reset it to one to start a new subarray.
- Update the prefix product with the current element during the left-to-right traversal.
- Update the suffix product with the current element during the right-to-left traversal.
- At each step, compute the maximum product using the current prefix and suffix products.
- Return the maximum product obtained after the traversal.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to find the product of
elements in maximum product subarray */
int maxProduct(vector<int>& nums) {
int n = nums.size();
int ans = INT_MIN; // to store the answer
// Indices to store the prefix and suffix multiplication
int prefix = 1, suffix = 1;
// Iterate on the elements of the given array
for(int i=0; i < n; i++) {
/* Resetting the prefix and suffix
multiplication if they turn out to be zero */
if(prefix == 0) prefix = 1;
if(suffix == 0) suffix = 1;
// update the prefix and suffix multiplication
prefix *= nums[i];
suffix *= nums[n-i-1];
// store the maximum as the answer
ans = max(ans, max(prefix, suffix));
}
// return the result
return ans;
}
};
int main() {
vector<int> nums = {4, 5, 3, 7, 1, 2};
// Creating an object of Solution class
Solution sol;
/* Function call to find the product of
elements in maximum product subarray */
int ans = sol.maxProduct(nums);
cout << "The product of elements in maximum product subarray is: " << ans;
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N), where N is the size of the array- Traversing the given array using single for loop takes linear time.
- Space Complexity:
O(1), as only couple of variables are used.