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.

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.