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:

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

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

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

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

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

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

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:

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

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

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

2. Finding Left Bounds: We iterate through nums from left to right to fill left 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]

3. Finding Right Bounds: We iterate through nums from right to left to fill right 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]

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

   1nums = [3, 1, 5, 6, 4, 2]
   2Look out for the cumulative sum: s = [0, 3, 4, 9, 15, 19, 21]

5. Computing Max Min-Product: We iterate over each element to calculate the max min-product by using left, right, and s.

   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.

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

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.