Maximum Subarray Min-Product: Monotonic Stack + Prefix Sums

LeetCode 1856 Maximum Subarray Min-Product is a great problem for combining two classic techniques: monotonic stacks and prefix sums. It is rated medium, but the trick is recognizing that you can reframe it as a "for each element, find the widest subarray where it is the minimum" problem. Once you see that, it becomes a close cousin of Largest Rectangle in Histogram.

The problem

The min-product of an array is defined as the minimum value in the array multiplied by the sum of all values. Given an array of positive integers nums, find the maximum min-product of any non-empty subarray. Return the answer modulo 10^9 + 7.

Input:  nums = [1, 2, 3, 2]
Output: 14

The subarray [2, 3, 2] has a minimum of 2 and a sum of 7. The min-product is 2 * 7 = 14, which is the largest across all subarrays.

The brute force

The naive approach: check every subarray, compute its minimum and sum, and track the maximum min-product.

def max_min_product_brute(nums):
    n = len(nums)
    MOD = 10**9 + 7
    best = 0
    for i in range(n):
        cur_min = nums[i]
        cur_sum = 0
        for j in range(i, n):
            cur_min = min(cur_min, nums[j])
            cur_sum += nums[j]
            best = max(best, cur_min * cur_sum)
    return best % MOD

This is O(n^2). For each starting index, you expand the subarray to the right, updating the running minimum and sum. It works for small inputs, but the array can have up to 100,000 elements, so we need O(n).

The key insight: fix the minimum

Instead of iterating over all subarrays, flip the question. For each element nums[i], ask: "What is the largest subarray where nums[i] is the minimum?" If you know that subarray, you can compute its sum (using prefix sums) and multiply by nums[i] to get the min-product.

Why does this cover all optimal answers? For any subarray, some element is the minimum. That element "owns" the subarray. By checking the best subarray for every possible minimum, you cover every case.

The problem reduces to two subproblems:

1. For each index i, find the widest subarray where nums[i] is the minimum. This means finding the nearest smaller element on the left and right. A monotonic stack solves this in O(n).
2. Compute the sum of any subarray in O(1). A prefix sum array handles this.

Building the prefix sum array

The prefix sum array lets you compute the sum of any subarray in O(1). Define prefix[0] = 0 and prefix[i] = nums[0] + nums[1] + ... + nums[i-1]. Then the sum of nums[l..r] is prefix[r+1] - prefix[l].

prefix = [0] * (n + 1)
for i in range(n):
    prefix[i + 1] = prefix[i] + nums[i]

For nums = [1, 2, 3, 2], the prefix array is [0, 1, 3, 6, 8]. The sum of nums[1..3] is prefix[4] - prefix[1] = 8 - 1 = 7.

The monotonic stack

Maintain a stack of indices in increasing order of value. When you encounter an element smaller than the top, the top can no longer extend its subarray to the right. Pop it and compute the min-product for that element.

When you pop index p at position i:

• The right boundary is i (the first smaller element to the right).
• The left boundary is the new stack top (the first smaller element to the left), or -1 if the stack is empty.
• The subarray where nums[p] is the minimum spans from left + 1 to right - 1.
• The sum of that subarray is prefix[right] - prefix[left + 1].
• The min-product is nums[p] * (prefix[right] - prefix[left + 1]).

After processing all elements, pop whatever remains on the stack using n as the right boundary.

Step-by-step walkthrough

Let's trace through nums = [1, 2, 3, 2] with prefix = [0, 1, 3, 6, 8]. We maintain an increasing monotonic stack and compute min-products when elements are popped.

Key observations:

• The stack stays increasing. Every time you push, the new value is at least as large as the top. When a smaller value arrives, you pop until the invariant is restored.
• Step 4 is where the first pop happens. When nums[3]=2 arrives, it pops index 2 (value 3). The subarray for value 3 is just [3] itself, giving min-product 9.
• The cleanup phase finds the answer. When we pop index 1 during cleanup, its subarray extends from index 1 to index 3, which is [2, 3, 2]. Min-product = 2 * 7 = 14.
• Each index is pushed once and popped once. The total work across all iterations is O(n).

The code

def maxSumMinProduct(nums):
    MOD = 10**9 + 7
    n = len(nums)

    # Build prefix sum array
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]

    stack = []
    best = 0

    for i in range(n):
        while stack and nums[i] < nums[stack[-1]]:
            p = stack.pop()
            left = stack[-1] if stack else -1
            total = prefix[i] - prefix[left + 1]
            best = max(best, nums[p] * total)
        stack.append(i)

    # Cleanup: pop remaining elements
    while stack:
        p = stack.pop()
        left = stack[-1] if stack else -1
        total = prefix[n] - prefix[left + 1]
        best = max(best, nums[p] * total)

    return best % MOD

Breaking it down:

1. Build the prefix sum array for O(1) range sum queries.
2. Walk through each element left to right, maintaining an increasing stack.
3. While the current element is smaller than the top: pop the top, compute the subarray sum using prefix sums, and update the best min-product.
4. Push the current index.
5. After the loop, pop all remaining elements. For each, the right boundary is n (end of array).
6. Return the result modulo 10^9 + 7.

Complexity analysis

Time: O(n). Building the prefix sum is O(n). Each index is pushed onto the stack once and popped once. The total work across the main loop and cleanup is O(n).

Space: O(n). The prefix array and stack each use O(n) space.

You trade O(n) space for an order-of-magnitude time improvement. For arrays up to 100,000 elements, the stack solution runs comfortably within time limits.

The building blocks

This problem combines two reusable patterns:

Monotonic stack for nearest smaller elements

The core loop is the same one from Largest Rectangle in Histogram:

while stack and nums[i] < nums[stack[-1]]:
    p = stack.pop()
    left = stack[-1] if stack else -1
    # process element p with boundaries (left, i)
stack.append(i)

When you pop index p, you know that i is the first smaller element to the right, and the new stack top is the first smaller element to the left. This is the fundamental monotonic stack pattern.

Prefix sum for range queries

prefix = [0] * (n + 1)
for i in range(n):
    prefix[i + 1] = prefix[i] + nums[i]
# sum of nums[l..r] = prefix[r + 1] - prefix[l]

This turns any range sum query into a constant-time subtraction. It pairs naturally with the monotonic stack, which gives you the boundaries for the range.

Edge cases

Before submitting, verify your solution handles:

• Single element [5]: the only subarray is [5]. Min-product = 5 * 5 = 25. But wait, it is 5 * 5 = 25 only if min-product means min * sum. With one element, min = sum = 5, so min-product = 25.
• All equal elements like [3, 3, 3]: the best subarray is the entire array. Min = 3, sum = 9, min-product = 27.
• Strictly increasing like [1, 2, 3, 4]: the entire array has min = 1 and sum = 10, giving min-product = 10. But the subarray [3, 4] has min = 3 and sum = 7, giving 21. And [4] alone gives 16. The stack correctly evaluates all candidates.
• Strictly decreasing like [4, 3, 2, 1]: similar analysis. The subarray [4, 3] gives 3 * 7 = 21, and [4] gives 16.
• Large values: since elements can be up to 10^7 and the array can have 10^5 elements, the intermediate product can reach about 10^12. In Python this is fine. In other languages, use 64-bit integers.

Common mistakes

1. Applying modulo too early. If you take mod during the comparison (best = max(best, (nums[p] * total) % MOD)), you can get wrong results because the mod reduces the value, making the max comparison incorrect. Compute the true product, take the max, then mod only at the end.

2. Using <= instead of < in the while condition. When there are duplicate values, using <= can cause incorrect boundary calculations. Using strict < means equal elements stay on the stack, which is safe because their subarrays overlap correctly.

3. Forgetting the cleanup phase. Elements still on the stack after the main loop have no smaller element to their right. You must pop them with right boundary n, or you miss candidates.

4. Off-by-one in the prefix sum formula. The sum of nums[left+1..right-1] is prefix[right] - prefix[left+1]. Getting the indices wrong by one position is a common bug. Trace through a small example to verify.

From understanding to recall

You now understand how the monotonic stack identifies the widest subarray where each element is the minimum, and how prefix sums give you the subarray sum in O(1). The algorithm has a clean structure: build the prefix array, run the stack loop, clean up, return the max. But the details matter. The boundary calculation when popping, the prefix sum indexing, and the modulo timing are all places where bugs hide.

Spaced repetition helps lock in these details. Instead of re-reading this explanation when a similar problem appears, you practice writing the stack loop and prefix sum from scratch at increasing intervals. After a few reps, the boundary formula and the cleanup phase become second nature.

Related posts

• Largest Rectangle in Histogram - Nearly identical monotonic stack structure, computing area instead of min-product
• Sum of Subarray Minimums - Uses the same "for each element, find where it is the minimum" idea with contribution counting
• Daily Temperatures - The classic introduction to monotonic stacks, using the same pop loop with a simpler computation

CodeBricks breaks the monotonic stack and prefix sum patterns into their reusable pieces and drills them individually. You type the pop loop and the range sum formula from scratch each time, building the muscle memory so that when you see Maximum Subarray Min-Product or a similar problem in an interview, the code flows without hesitation.