1856. Maximum Subarray Min-Product
Problem Description
The goal in this LeetCode problem is to find the maximum "min-product" of any non-empty contiguous subarray from an input array nums
. The "min-product" is defined as the product of the minimum value in the subarray and the sum of the subarray. To put it another way, for any given subarray, you identify the smallest element and multiply it by the sum of all the elements in the subarray. You must consider all possible subarrays within the original array to determine which gives the maximum "min-product."
The maximum "min-product" found should also be returned modulo (10^9 + 7), as this could be a very large number and we're often asked to return such large results in a manageable form by using a modulo operation.
The problem specifies that the maximum "min-product" should be computed before taking the modulo. Additionally, the conditions assure that the result prior to applying the modulo operation will fit in a 64-bit signed integer.
A key detail to note is that subarrays are contiguous slices of the original array, meaning you can't skip elements when forming a subarray.
Intuition
To solve this problem, we must efficiently find the "min-product" of all subarrays, which means we need to know the minimum value and the sum of these subarrays. A brute force approach would involve checking every possible subarray which would not be efficient, especially for large arrays.
Thus, the intuition is to use a different strategy to determine the minimum value's scope of influence within the array. Essentially, for each element, we want to find out how far to the left and to the right it remains the minimum element. This will define the "window" or "stretch" of the subarray for which this element is the minimum.
For the given element at index i
, this means finding the closest element to the left that is smaller than nums[i]
(if any) and finding the closest element to the right that is smaller or equal to nums[i]
. These two indicators give us the boundaries of the potential subarrays where nums[i]
is the smallest element.
To achieve this efficiently, we utilize a monotonically decreasing stack that helps us find these boundaries through a single pass of the array from left to right and another pass from right to left.
The sum of any subarray can be efficiently obtained by using the concept of prefix sums, which is a cumulative sum of the array elements. By storing these sums, we can calculate the sum of any subarray in constant time by subtracting the appropriate prefix sums.
Combining these two techniques—finding the stretch of the minimum element with a stack and the use of prefix sums for quick subarray sum calculation—enables us to compute the "min-product" for all relevant subarrays efficiently.
This combined strategy leads to an algorithm that only needs to pass through the array a constant number of times, substantially improving the efficiency compared to a brute force approach which would require passing through the array a number of times proportional to the number of subarrays, which is not feasible for large arrays.
Learn more about Stack, Prefix Sum and Monotonic Stack patterns.
Solution Approach
The provided solution approach employs a stack to efficiently determine the left and right boundaries within which each element of the array is the minimum value. By doing so, we essentially calculate the stretch or the window for each element where it remains the minimum. A prefix sum array is also used to calculate the sum of elements in constant time. Here's how the approach is implemented step by step:
-
Initializing Stacks and Boundary Arrays: Two empty stacks are used, and two arrays named
left
andright
are initialized to store the left and right boundaries. For every indexi
inleft
, the value is initialized to-1
, indicating that there is no smaller element to the left. Similarly, inright
, every index is initialized withn
, representing that there's no smaller or equal element to the right by default. -
Finding Left Bounds: Iterating through the array
nums
from left to right, we use the stack to maintain a list of indices where the corresponding values innums
are in a monotonically decreasing order. When encountering an element whose value is less than or equal to the last element's value in the stack, we pop the stack. By popping the stack, we ensure that for each indexi
,left[i]
would hold the index of the nearest element to the left that is smaller than the current element. -
Finding Right Bounds: Starting from the end of the array and moving leftwards, we employ a similar strategy with a new stack. This stack helps to find for each element
nums[i]
, the index of the closest smaller or equal element to the right. We iterate backwards and each time we find an element smaller than the current element, we pop the stack and update theright
array accordingly. -
Calculating Prefix Sums: We create a prefix sum array
s
from thenums
array to have sums of elements up to every index. Prefix sums let us calculate the sum of elements between any two indices in constant time. -
Computing Max Min-Product: With the left and right boundaries, and the prefix sum array ready, for each index
i
, we now calculate the min-product. The minimum elementnums[i]
multiplied by the sum of the subarray fromleft[i] + 1
toright[i] - 1
, which is computed ass[right[i]] - s[left[i] + 1]
. We find the maximum of these min-products. -
Applying Modulo and Return: The maximum min-product found from step 5 is then taken modulo (10^9 + 7) before returning as the final answer.
The core algorithmic patterns used in this solution include:
- Monotonic Stack: To find the next smaller element efficiently while traversing an array.
- Prefix Sum: To calculate the sum of subarrays in constant time.
- Iterative Search: To combine the results from the monotonic stack and prefix sums to compute the min-products for all subarrays and find the maximum.
The data structure used is a simple list to implement stacks and store the prefix sums and boundaries.
By applying these algorithms and patterns, the solution minimizes redundant calculations and efficiently computes the desired max min-product, even for large input arrays.
The solution's time complexity is (O(n)), where n
is the length of the array, due to the single pass needed for finding boundaries and the prefix sum calculation, and the space complexity is also (O(n)) for storing the additional arrays for boundaries and prefix sums.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through a small example to illustrate the solution approach. We will use the following input array nums
to understand the process:
1[3, 1, 5, 6, 4, 2]
-
Initializing Stacks and Boundary Arrays: We initialize two empty stacks: one for finding left bounds and one for right bounds. We also initialize two arrays,
left
andright
, of the same length asnums
, filled with-1
andnums.length
(6), respectively.1left = [-1, -1, -1, -1, -1, -1] 2right = [ 6, 6, 6, 6, 6, 6] 3stacks (left and right) = []
-
Finding Left Bounds: We iterate through
nums
from left to right to fillleft
array.1i = 0: stack = [], left = [-1, ..], nums[i] = 3 2i = 1: stack = [0], left = [-1, -1, ..], nums[i] = 1 (3 > 1, pop index 0) 3i = 2: stack = [1], left = [-1, -1, 1, ..], nums[i] = 5 4i = 3: stack = [1, 2], left = [-1, -1, 1, 2, ..], nums[i] = 6 5i = 4: stack = [1, 2, 3], left = [-1, -1, 1, 2, 3, ..], nums[i] = 4 (6 > 4, pop index 3) 6i = 5: stack = [1, 4], left = [-1, -1, 1, 2, 3, 4], nums[i] = 2 (4 > 2, pop index 4)
Final
left
after completing iteration:1left = [-1, -1, 1, 2, 3, 4]
-
Finding Right Bounds: We iterate through
nums
from right to left to fillright
array.1i = 5: stack = [], right = [.., 5], nums[i] = 2 2i = 4: stack = [5], right = [.., 4, 5], nums[i] = 4 (2 < 4, push index 5) 3i = 3: stack = [4], right = [.., 3, 4, 5], nums[i] = 6 (4 < 6, push index 4) 4i = 2: stack = [3, 4], right = [.., 2, 3, 4, 5], nums[i] = 5 (6 > 5, pop index 3) 5i = 1: stack = [2], right = [.., 1, 2, 3, 4, 5], nums[i] = 1 (5 > 1, pop index 2) 6i = 0: stack = [1], right = [1, .., 2, 3, 4, 5], nums[i] = 3 (1 < 3, push index 1)
Final
right
after completing iteration:1right = [1, 2, 3, 4, 5, 6]
-
Calculating Prefix Sums: Create the prefix sum array
s
by iterating overnums
.1nums = [3, 1, 5, 6, 4, 2] 2Look out for the cumulative sum: s = [0, 3, 4, 9, 15, 19, 21]
-
Computing Max Min-Product: We iterate over each element to calculate the max min-product by using
left
,right
, ands
.1For nums[0] (3): min-product = nums[0] * (s[right[0]] - s[left[0] + 1]) = 3 * (4 - 0) = 12 2For nums[1] (1): min-product = nums[1] * (s[right[1]] - s[left[1] + 1]) = 1 * (21 - 0) = 21 3... 4For nums[5] (2): min-product = nums[5] * (s[right[5]] - s[left[5] + 1]) = 2 * (21 - 19) = 4
Calculate the maximum min-product out of all the results:
1The maximum min-product is for nums[1] which is 21.
-
Applying Modulo and Return: Take the result modulo (10^9 + 7) and return the final answer.
1max min-product = 21 % (10^9 + 7) = 21
Hence, the return value for this input would be 21
, which is the maximum min-product for any subarray within the array [3, 1, 5, 6, 4, 2]
.
Solution Implementation
1from itertools import accumulate
2from typing import List
3
4class Solution:
5 def max_sum_min_product(self, nums: List[int]) -> int:
6 # Initialize some basic variables
7 num_elements = len(nums)
8 left_bound = [-1] * num_elements # Array to store the index of the previous smaller element for each element
9 right_bound = [num_elements] * num_elements # Array to store the index of the next smaller element for each element
10 stack = []
11
12 # Iterating from left to right to fill left_bound array
13 for i, value in enumerate(nums):
14 # Pop elements from the stack if they are not smaller than the current value
15 while stack and nums[stack[-1]] >= value:
16 stack.pop()
17 if stack:
18 left_bound[i] = stack[-1]
19 stack.append(i) # Push current index to stack
20
21 stack = [] # Reset the stack for the next iteration
22
23 # Iterating from right to left to fill right_bound array
24 for i in range(num_elements - 1, -1, -1):
25 # Pop elements from the stack if they are not strictly smaller than the current value
26 while stack and nums[stack[-1]] > nums[i]:
27 stack.pop()
28 if stack:
29 right_bound[i] = stack[-1]
30 stack.append(i) # Push current index to stack
31
32 # Prefix sum of nums for range sum queries
33 prefix_sum = list(accumulate(nums, initial=0))
34
35 # Modulo for large numbers to not exceed the upper limit of a 32-bit integer
36 modulo = 10**9 + 7
37
38 # Calculate the maximum sum of the minimum product
39 max_sum = max((prefix_sum[right_bound[i]] - prefix_sum[left_bound[i] + 1]) * value for i, value in enumerate(nums)) % modulo
40
41 return max_sum
42
43# Example usage:
44# solution = Solution()
45# result = solution.max_sum_min_product([1,2,3,2])
46# print(result)
47
1class Solution {
2 public int maxSumMinProduct(int[] nums) {
3 // Initialize the length of the array.
4 int n = nums.length;
5
6 // Arrays to store the indexes of the next smaller element to the left and right.
7 int[] leftSmallerIndex = new int[n];
8 int[] rightSmallerIndex = new int[n];
9
10 // Initialize indexes as -1 for the left and n for the right.
11 Arrays.fill(leftSmallerIndex, -1);
12 Arrays.fill(rightSmallerIndex, n);
13
14 // Stack to keep track of the indexes for which we haven't found a smaller element yet.
15 Deque<Integer> stack = new ArrayDeque<>();
16
17 // Calculate the indexes of the next smaller elements on the left.
18 for (int i = 0; i < n; ++i) {
19 while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
20 stack.pop();
21 }
22 if (!stack.isEmpty()) {
23 leftSmallerIndex[i] = stack.peek();
24 }
25 stack.push(i);
26 }
27
28 // Clear the stack for the next iteration.
29 stack.clear();
30
31 // Calculate the indexes of the next smaller elements on the right.
32 for (int i = n - 1; i >= 0; --i) {
33 while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
34 stack.pop();
35 }
36 if (!stack.isEmpty()) {
37 rightSmallerIndex[i] = stack.peek();
38 }
39 stack.push(i);
40 }
41
42 // Create and populate the prefix sums array which holds the sum until the ith element.
43 long[] prefixSums = new long[n + 1];
44 for (int i = 0; i < n; ++i) {
45 prefixSums[i + 1] = prefixSums[i] + nums[i];
46 }
47
48 // Variable to store the maximum sum of the minimum product found.
49 long maxSumMinProduct = 0;
50
51 // Find the maximum sum of the minimum product by iterating through each element.
52 for (int i = 0; i < n; ++i) {
53 long sum = prefixSums[rightSmallerIndex[i]] - prefixSums[leftSmallerIndex[i] + 1];
54 maxSumMinProduct = Math.max(maxSumMinProduct, nums[i] * sum);
55 }
56
57 // Define the modulo according to the problem's requirement.
58 final int mod = (int) 1e9 + 7;
59
60 // Return the maximum sum of the minimum product modulo 1e9+7.
61 return (int) (maxSumMinProduct % mod);
62 }
63}
64
1class Solution {
2public:
3 int maxSumMinProduct(vector<int>& nums) {
4 int n = nums.size();
5 // Initialize `left` and `right` to keep track of the boundaries
6 // within which each number is the smallest
7 vector<int> left(n, -1);
8 vector<int> right(n, n);
9 stack<int> stack;
10
11 // Find the previous smaller element for each number
12 for (int i = 0; i < n; ++i) {
13 while (!stack.empty() && nums[stack.top()] >= nums[i]) {
14 stack.pop();
15 }
16 if (!stack.empty()) {
17 left[i] = stack.top();
18 }
19 stack.push(i);
20 }
21
22 // Clear the stack for the next step
23 stack = stack<int>();
24
25 // Find the next smaller element for each number
26 for (int i = n - 1; i >= 0; --i) {
27 while (!stack.empty() && nums[stack.top()] > nums[i]) {
28 stack.pop();
29 }
30 if (!stack.empty()) {
31 right[i] = stack.top();
32 }
33 stack.push(i);
34 }
35
36 // `prefix_sum` stores the cumulative sum of `nums`
37 long long prefix_sum[n + 1];
38 prefix_sum[0] = 0;
39 for (int i = 0; i < n; ++i) {
40 prefix_sum[i + 1] = prefix_sum[i] + nums[i];
41 }
42
43 // Calculate the answer by considering each `nums[i]` as the minimum in
44 // the subarray and multiplying it with the sum of the subarray defined by
45 // the range `left[i] + 1` to `right[i] - 1`
46 long long max_product = 0;
47 for (int i = 0; i < n; ++i) {
48 max_product = max(max_product,
49 nums[i] * (prefix_sum[right[i]] - prefix_sum[left[i] + 1]));
50 }
51
52 // Apply modulo as per problem's requirement
53 const int mod = 1e9 + 7;
54 return max_product % mod;
55 }
56};
57
1function maxSumMinProduct(nums: number[]): number {
2 // Initialize the array length.
3 const n = nums.length;
4
5 // Create arrays to store the previous smaller and next smaller elements' indices.
6 const prevSmallerIndices: number[] = new Array(n).fill(-1);
7 const nextSmallerIndices: number[] = new Array(n).fill(n);
8
9 // Stack to keep track of the indices while finding prev and next smaller.
10 let stack: number[] = [];
11
12 // Find the previous smaller element's index for each element.
13 for (let i = 0; i < n; ++i) {
14 while (stack.length && nums[stack[stack.length - 1]] >= nums[i]) {
15 stack.pop();
16 }
17 if (stack.length) {
18 prevSmallerIndices[i] = stack[stack.length - 1];
19 }
20 stack.push(i);
21 }
22
23 // Reset the stack to find the next smaller elements.
24 stack = [];
25
26 // Find the next smaller element's index for each element.
27 for (let i = n - 1; i >= 0; --i) {
28 while (stack.length && nums[stack[stack.length - 1]] > nums[i]) {
29 stack.pop();
30 }
31 if (stack.length) {
32 nextSmallerIndices[i] = stack[stack.length - 1];
33 }
34 stack.push(i);
35 }
36
37 // Create and fill the prefix sum array.
38 const prefixSums: number[] = new Array(n + 1).fill(0);
39 for (let i = 0; i < n; ++i) {
40 prefixSums[i + 1] = prefixSums[i] + nums[i];
41 }
42
43 // Initialize the answer as a BigInt.
44 let answer: bigint = 0n;
45 // Define the modulo value.
46 const mod = 10 ** 9 + 7;
47
48 // Calculate the maximum sum of the minimum product.
49 for (let i = 0; i < n; ++i) {
50 const rangeSum = prefixSums[nextSmallerIndices[i]] - prefixSums[prevSmallerIndices[i] + 1];
51 const minProduct = BigInt(nums[i]) * BigInt(rangeSum);
52 if (answer < minProduct) {
53 answer = minProduct;
54 }
55 }
56
57 // Return the result modulo 10^9 + 7.
58 return Number(answer % BigInt(mod));
59}
60
Time and Space Complexity
Time Complexity
The time complexity of the solution is mainly determined by three separate for-loops that do not nest within each other.
The first loop goes through the elements of nums
to find the previous lesser element for each item. This loop runs in O(n)
time since each element is processed once, and elements are added to and popped from the stack in constant time. The same applies to the second loop, which finds the next lesser element for each item in nums
, operating in O(n)
time.
The third part of the solution is the computation of prefix sums and the finding of the maximum product. The prefix sum computation is O(n)
because it makes a single pass through the nums
. Then, finding the maximum sum of the minimum product is done with a single loop through nums
again, taking O(n)
time.
Thus, the total time complexity expresses as O(n) + O(n) + O(n) + O(n)
, which simplifies to O(n)
.
Space Complexity
The space complexity is mainly due to the additional data structures used: left
, right
, stk
, and s
.
- The arrays
left
andright
each take upO(n)
space. - The stack
stk
can potentially store alln
elements in the worst case, resulting inO(n)
space. - The prefix sum array
s
isO(n)
.
Therefore, the space complexity combines these O(n) + O(n) + O(n) + O(n)
terms, which simplifies to O(n)
overall.
Learn more about how to find time and space complexity quickly using problem constraints.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
Monotonic Stack Deque Intro If you'd prefer a video div class responsive iframe iframe src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div The word monotonic means a list or
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.