Problem Description

Given an array of integers nums, you need to find the maximum min-product among all possible non-empty subarrays.

The min-product of an array is defined as the minimum value in the array multiplied by the sum of all elements in the array.

For example, if we have the array [3,2,5]:

• The minimum value is 2
• The sum of all elements is 3 + 2 + 5 = 10
• The min-product is 2 * 10 = 20

Your task is to:

1. Consider all possible contiguous subarrays of the given array
2. Calculate the min-product for each subarray
3. Return the maximum min-product found

Since the answer can be very large, return the result modulo 10^9 + 7. Note that you should find the maximum min-product first, then apply the modulo operation.

A subarray is a contiguous sequence of elements from the array. For instance, if nums = [1,2,3,4], then [2,3] is a subarray, but [1,3] is not (elements are not contiguous).

The key insight is that for each element in the array, we can consider it as the minimum element of some subarray. We need to find the optimal subarray boundaries where this element remains the minimum, which would maximize the sum and thus the min-product for that particular minimum value.

Intuition

The key observation is that we want to maximize the product of (minimum value) × (sum of subarray). Since we're dealing with a product, we need to think about how to balance these two factors.

For each element nums[i] in the array, let's consider what happens if we fix it as the minimum value of a subarray. Once we fix the minimum, we want to maximize the sum of the subarray while ensuring nums[i] remains the minimum. This means we should extend the subarray as far as possible to the left and right, including all elements that are greater than or equal to nums[i].

Think of it this way: if nums[i] is going to be our minimum value, we should be greedy and include as many elements as possible in our subarray (to maximize the sum), but we must stop when we encounter an element smaller than nums[i] (otherwise nums[i] wouldn't be the minimum anymore).

For example, if we have [3, 1, 5, 6, 4, 2] and we're considering 4 as the minimum:

• We can extend left to include 6 and 5 (both ≥ 4)
• We stop at 1 on the left (1 < 4)
• We can't extend right because 2 < 4
• So the subarray would be [5, 6, 4] with min-product = 4 × (5+6+4) = 60

This leads us to the problem: for each element, we need to find:

1. Left boundary: the rightmost position to the left where an element is strictly less than nums[i]
2. Right boundary: the leftmost position to the right where an element is less than or equal to nums[i]

The reason for the asymmetry (strictly less on the left, less than or equal on the right) is to avoid counting the same subarray twice when we have duplicate values.

Finding these boundaries efficiently for all elements suggests using a monotonic stack - a classic technique for finding the next/previous smaller element. We can use the stack to maintain elements in increasing order, which helps us quickly identify boundaries.

To calculate the sum efficiently, we use a prefix sum array so that the sum of any subarray can be computed in O(1) time as s[right] - s[left].

Learn more about Stack, Prefix Sum and Monotonic Stack patterns.

Solution Approach

The solution uses monotonic stacks to find boundaries and prefix sums for efficient range sum calculation.

Step 1: Find Left Boundaries

We traverse the array from left to right with a monotonic stack to find left[i] - the rightmost position to the left of i where nums[left[i]] < nums[i].

left = [-1] * n  # Initialize with -1 (no element to the left)
stk = []
for i, x in enumerate(nums):
    while stk and nums[stk[-1]] >= x:
        stk.pop()  # Remove elements >= current element
    if stk:
        left[i] = stk[-1]  # Top of [stack](/problems/stack_intro) is the rightmost smaller element
    stk.append(i)

The stack maintains indices in increasing order of their values. When we encounter nums[i], we pop all elements from the stack that are greater than or equal to nums[i]. The remaining top element (if any) is the rightmost element smaller than nums[i].

Step 2: Find Right Boundaries

Similarly, we traverse from right to left to find right[i] - the leftmost position to the right of i where nums[right[i]] <= nums[i].

right = [n] * n  # Initialize with n (no element to the right)
stk = []
for i in range(n - 1, -1, -1):
    while stk and nums[stk[-1]] > nums[i]:
        stk.pop()  # Remove elements > current element
    if stk:
        right[i] = stk[-1]  # Top of [stack](/problems/stack_intro) is the leftmost smaller or equal element
    stk.append(i)

Note the subtle difference: we use > instead of >= to handle duplicates correctly and avoid counting the same subarray multiple times.

Step 3: Calculate Prefix Sums

We build a prefix sum array where s[i] represents the sum of the first i elements:

s = list(accumulate(nums, initial=0))

This allows us to calculate the sum of subarray [left[i]+1, right[i]-1] as s[right[i]] - s[left[i] + 1] in O(1) time.

Step 4: Find Maximum Min-Product

For each element nums[i] as the minimum value, the subarray extends from left[i] + 1 to right[i] - 1. The min-product is:

min_product = nums[i] * (s[right[i]] - s[left[i] + 1])

We calculate this for all positions and return the maximum value modulo 10^9 + 7:

return max((s[right[i]] - s[left[i] + 1]) * x for i, x in enumerate(nums)) % mod

Time Complexity: O(n) - each element is pushed and popped from the stack at most once.
Space Complexity: O(n) - for the left, right, s arrays and the stack.

Example Walkthrough

Let's walk through the solution with the array nums = [2, 3, 3, 1, 2].

Step 1: Find Left Boundaries

We traverse left to right with a monotonic stack to find the rightmost smaller element to the left of each position.

• i=0, x=2: stack=[], no smaller element to left, left[0]=-1, stack=[0]
• i=1, x=3: stack=[0], nums[0]=2 < 3, left[1]=0, stack=[0,1]
• i=2, x=3: stack=[0,1], nums[1]=3 >= 3 so pop 1, nums[0]=2 < 3, left[2]=0, stack=[0,2]
• i=3, x=1: stack=[0,2], nums[2]=3 >= 1 so pop 2, nums[0]=2 >= 1 so pop 0, stack=[], left[3]=-1, stack=[3]
• i=4, x=2: stack=[3], nums[3]=1 < 2, left[4]=3, stack=[3,4]

Result: left = [-1, 0, 0, -1, 3]

Step 2: Find Right Boundaries

We traverse right to left to find the leftmost smaller or equal element to the right.

• i=4, x=2: stack=[], no element to right, right[4]=5, stack=[4]
• i=3, x=1: stack=[4], nums[4]=2 > 1, pop 4, stack=[], right[3]=5, stack=[3]
• i=2, x=3: stack=[3], nums[3]=1 <= 3, right[2]=3, stack=[3,2]
• i=1, x=3: stack=[3,2], nums[2]=3 > 3 is false, right[1]=2, stack=[3,2,1]
• i=0, x=2: stack=[3,2,1], nums[1]=3 > 2, pop 1, nums[2]=3 > 2, pop 2, nums[3]=1 <= 2, right[0]=3, stack=[3,0]

Result: right = [3, 2, 3, 5, 5]

Step 3: Calculate Prefix Sums

s = [0, 2, 5, 8, 9, 11] where s[i] = sum of first i elements

Step 4: Calculate Min-Products

For each position i, the subarray extends from left[i]+1 to right[i]-1:

• i=0: subarray [0,2], sum = s[3] - s[0] = 8 - 0 = 8, min-product = 2 × 8 = 16
• i=1: subarray [1,1], sum = s[2] - s[1] = 5 - 2 = 3, min-product = 3 × 3 = 9
• i=2: subarray [1,2], sum = s[3] - s[1] = 8 - 2 = 6, min-product = 3 × 6 = 18
• i=3: subarray [0,4], sum = s[5] - s[0] = 11 - 0 = 11, min-product = 1 × 11 = 11
• i=4: subarray [4,4], sum = s[5] - s[4] = 11 - 9 = 2, min-product = 2 × 2 = 4

Maximum min-product = 18 (from position i=2)

The key insight is that for element 3 at position 2, we can extend the subarray to include position 1 (also value 3) but must stop at position 3 (value 1 < 3). This gives us the subarray [3,3] with minimum 3 and sum 6, yielding the maximum min-product of 18.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of several linear passes through the array:

• First monotonic stack traversal to find left boundaries: Each element is pushed and popped from the stack at most once, resulting in O(n) operations
• Second monotonic stack traversal to find right boundaries: Similarly, each element is pushed and popped at most once, giving O(n) operations
• Building the prefix sum array using accumulate: O(n) time
• Final iteration to calculate the maximum sum-min product: O(n) time to iterate through all elements

Since all operations are linear and performed sequentially, the overall time complexity is O(n) + O(n) + O(n) + O(n) = O(n).

Space Complexity: O(n)

The algorithm uses the following auxiliary data structures:

• left array of size n: O(n) space
• right array of size n: O(n) space
• stk for monotonic stack operations: At most n elements, so O(n) space
• s prefix sum array of size n+1: O(n) space

The total space complexity is O(n) + O(n) + O(n) + O(n) = O(n), where n is the length of the input array nums.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Duplicate Elements

One of the most common mistakes is using the same comparison operator for both left and right boundary calculations. This can lead to counting the same subarray multiple times when duplicate elements exist.

Incorrect approach:

# Both using >= operator
while stack and nums[stack[-1]] >= value:  # Left boundary
while stack and nums[stack[-1]] >= nums[i]:  # Right boundary

Why it's wrong: If we have duplicates like [2, 2, 2], using >= for both boundaries means each 2 could claim the entire array as its domain, causing the same subarray to be counted three times.

Correct approach:

# Left boundary: use >=
while stack and nums[stack[-1]] >= value:
    stack.pop()

# Right boundary: use > (strictly greater)
while stack and nums[stack[-1]] > nums[i]:
    stack.pop()

This ensures that when duplicates exist, only the leftmost occurrence can extend to include all duplicates, preventing double counting.

2. Applying Modulo Too Early

Incorrect approach:

# Applying modulo during calculation
max_product = 0
for i, value in enumerate(nums):
    product = ((prefix_sum[right_boundary[i]] - prefix_sum[left_boundary[i] + 1]) * value) % MOD
    max_product = max(max_product, product)
return max_product

Why it's wrong: The problem asks to find the maximum first, then apply modulo. Applying modulo during calculation can change the comparison results since (a % MOD) > (b % MOD) doesn't necessarily mean a > b.

Correct approach:

# Find maximum first, then apply modulo
max_product = max(
    (prefix_sum[right_boundary[i]] - prefix_sum[left_boundary[i] + 1]) * value 
    for i, value in enumerate(nums)
)
return max_product % MOD

3. Off-by-One Errors in Boundary Indices

Common mistake: Confusion about whether boundaries are inclusive or exclusive.

Key points to remember:

• left_boundary[i] is the index of an element strictly smaller than nums[i]
• right_boundary[i] is the index of an element smaller than or equal to nums[i]
• The valid subarray where nums[i] is minimum spans from left_boundary[i] + 1 to right_boundary[i] - 1 (inclusive)
• For prefix sum calculation: sum[l, r] = prefix_sum[r + 1] - prefix_sum[l]

4. Integer Overflow in Other Languages

While Python handles large integers automatically, in languages like Java or C++, the multiplication can overflow:

Solution for other languages:

// Java example - use long type
long product = ((long)rangeSum * nums[i]) % MOD;

5. Incorrect Initialization of Boundaries

Incorrect:

left_boundary = [0] * n  # Wrong! This suggests element 0 is always a left boundary
right_boundary = [n-1] * n  # Wrong! This suggests element n-1 is always a right boundary

Correct:

left_boundary = [-1] * n  # -1 indicates no smaller element to the left
right_boundary = [n] * n   # n indicates no smaller element to the right

These sentinel values correctly handle edge cases where an element is the smallest in its extending range.