1856. Maximum Subarray Min-Product

MediumStackArrayPrefix SumMonotonic Stack

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 and right are initialized to store the left and right boundaries. For every index i in left, the value is initialized to -1, indicating that there is no smaller element to the left. Similarly, in right, every index is initialized with n, 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 in nums 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 index i, 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 the right array accordingly.
Calculating Prefix Sums: We create a prefix sum array s from the nums 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 element nums[i] multiplied by the sum of the subarray from left[i] + 1 to right[i] - 1, which is computed as s[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 Evaluator

Example 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:

[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 and right, of the same length as nums, filled with -1 and nums.length (6), respectively.

left  = [-1, -1, -1, -1, -1, -1]
right = [ 6,  6,  6,  6,  6,  6]
stacks (left and right) = []

Finding Left Bounds: We iterate through nums from left to right to fill left array.

i = 0: stack = [],   left = [-1, ..], nums[i] = 3
i = 1: stack = [0],  left = [-1, -1, ..], nums[i] = 1 (3 > 1, pop index 0)
i = 2: stack = [1],  left = [-1, -1, 1, ..], nums[i] = 5
i = 3: stack = [1, 2],  left = [-1, -1, 1, 2, ..], nums[i] = 6
i = 4: stack = [1, 2, 3],  left = [-1, -1, 1, 2, 3, ..], nums[i] = 4 (6 > 4, pop index 3)
i = 5: stack = [1, 4],  left = [-1, -1, 1, 2, 3, 4], nums[i] = 2 (4 > 2, pop index 4)

Final left after completing iteration:

left = [-1, -1, 1, 2, 3, 4]

Finding Right Bounds: We iterate through nums from right to left to fill right array.

i = 5: stack = [],   right = [.., 5], nums[i] = 2
i = 4: stack = [5],  right = [.., 4, 5], nums[i] = 4 (2 < 4, push index 5)
i = 3: stack = [4],  right = [.., 3, 4, 5], nums[i] = 6 (4 < 6, push index 4)
i = 2: stack = [3, 4],  right = [.., 2, 3, 4, 5], nums[i] = 5 (6 > 5, pop index 3)
i = 1: stack = [2],  right = [.., 1, 2, 3, 4, 5], nums[i] = 1 (5 > 1, pop index 2)
i = 0: stack = [1],  right = [1, .., 2, 3, 4, 5], nums[i] = 3 (1 < 3, push index 1)

Final right after completing iteration:

right = [1, 2, 3, 4, 5, 6]

Calculating Prefix Sums: Create the prefix sum array s by iterating over nums.

nums = [3, 1, 5, 6, 4, 2]
Look 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, and s.

For nums[0] (3): min-product = nums[0] * (s[right[0]] - s[left[0] + 1]) = 3 * (4 - 0) = 12
For nums[1] (1): min-product = nums[1] * (s[right[1]] - s[left[1] + 1]) = 1 * (21 - 0) = 21
...
For 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:

The 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.

max 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 and right each take up O(n) space.
The stack stk can potentially store all n elements in the worst case, resulting in O(n) space.
The prefix sum array s is O(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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: