LeetCode 1856 - Maximum Subarray Min-Product

The problem asks us to find the maximum min-product of any contiguous subarray of a given integer array nums. The min-product of a subarray is defined as the minimum value in that subarray multiplied by the sum of all elements in that subarray.

leetcodemediumarraystackmonotonic-stackprefix-sum

LeetCode Problem 1856

Difficulty: 🟡 Medium
Topics: Array, Stack, Monotonic Stack, Prefix Sum

Solution

Problem Understanding

The problem asks us to find the maximum min-product of any contiguous subarray of a given integer array nums. The min-product of a subarray is defined as the minimum value in that subarray multiplied by the sum of all elements in that subarray. We are asked to return this maximum value modulo 10^9 + 7.

In simpler terms, given nums, we need to consider every possible contiguous subarray, calculate its sum, determine its minimum value, multiply these two numbers, and keep track of the largest result. The modulo operation only applies to the final maximum value.

The input nums can have up to 10^5 elements, each as large as 10^7. This means any brute-force approach that examines all subarrays will be far too slow. Since the constraints guarantee the result fits in a 64-bit integer, we don’t need to worry about intermediate overflow in Python or Go if using 64-bit integers.

Important edge cases include:

  1. Arrays of length 1, where the subarray is the array itself.
  2. Arrays with all elements equal, where every subarray has the same minimum.
  3. Arrays with strictly increasing or decreasing sequences, which affect how far a minimum can extend in a contiguous subarray.

Approaches

Brute Force

The brute-force approach is straightforward: iterate over all possible subarrays, compute the sum and minimum for each subarray, calculate the min-product, and update the maximum. This is correct but inefficient. Calculating all subarrays leads to O(n^2) subarrays, and computing the minimum and sum for each takes O(n) in a naive way. This results in O(n^3) time complexity in the worst case, which is not feasible for n = 10^5.

Optimal Approach

The key insight is to recognize that the problem is similar to the Largest Rectangle in Histogram problem. Instead of maximizing area, we maximize min * sum. We can use a monotonic increasing stack to determine, for each element, the range of subarrays where this element is the minimum. Once the left and right boundaries for each element are found, we can compute the subarray sum using prefix sums efficiently.

This reduces the problem to:

  1. Compute prefix sums of nums.
  2. Use a monotonic stack to find the first smaller element to the left and first smaller element to the right for each index.
  3. For each index i, calculate the sum of the subarray [left[i]+1, right[i]-1] using prefix sums, multiply by nums[i], and update the maximum.

This approach works in O(n) time and O(n) space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Checks every subarray explicitly
Optimal O(n) O(n) Monotonic stack + prefix sum

Algorithm Walkthrough

  1. Compute prefix sums of nums to allow O(1) subarray sum queries. This is done as prefix[i] = prefix[i-1] + nums[i].
  2. Initialize a monotonic increasing stack. The stack stores indices of elements in increasing order of their value.
  3. Iterate through nums:
  • While the current element is smaller than the element at the top of the stack, pop the stack.
  • The popped index corresponds to a minimum element of a subarray.
  • The left boundary is either the new top of the stack or -1 if the stack is empty.
  • The right boundary is the current index.
  • Compute the sum of the subarray between these boundaries using prefix sums.
  • Update the maximum min-product if nums[popped] * subarray_sum is larger.
  1. Handle remaining elements in the stack after iteration. For these, the right boundary is the end of the array.
  2. Return maximum min-product modulo 10^9 + 7.

Why it works: Each element is considered as the minimum in a subarray extending as far left and right as possible without encountering a smaller element. This guarantees we explore the largest subarray for which each number is the minimum exactly once, producing the correct maximum min-product.

Python Solution

from typing import List

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        
        # Compute prefix sums
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i+1] = prefix[i] + nums[i]
        
        stack = []
        max_product = 0
        
        for i in range(n):
            while stack and nums[stack[-1]] > nums[i]:
                idx = stack.pop()
                left = stack[-1] if stack else -1
                sub_sum = prefix[i] - prefix[left+1]
                max_product = max(max_product, nums[idx] * sub_sum)
            stack.append(i)
        
        while stack:
            idx = stack.pop()
            left = stack[-1] if stack else -1
            sub_sum = prefix[n] - prefix[left+1]
            max_product = max(max_product, nums[idx] * sub_sum)
        
        return max_product % MOD

Explanation: The prefix sum array allows O(1) subarray sum queries. The stack ensures we efficiently find left and right boundaries for each minimum. We compute the min-product whenever an element is popped, guaranteeing each element is treated as the minimum of the maximal subarray possible.

Go Solution

func maxSumMinProduct(nums []int) int {
    const MOD int = 1e9 + 7
    n := len(nums)
    
    prefix := make([]int64, n+1)
    for i := 0; i < n; i++ {
        prefix[i+1] = prefix[i] + int64(nums[i])
    }
    
    stack := []int{}
    var maxProduct int64 = 0
    
    for i := 0; i < n; i++ {
        for len(stack) > 0 && nums[stack[len(stack)-1]] > nums[i] {
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            left := -1
            if len(stack) > 0 {
                left = stack[len(stack)-1]
            }
            subSum := prefix[i] - prefix[left+1]
            product := int64(nums[idx]) * subSum
            if product > maxProduct {
                maxProduct = product
            }
        }
        stack = append(stack, i)
    }
    
    for len(stack) > 0 {
        idx := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        left := -1
        if len(stack) > 0 {
            left = stack[len(stack)-1]
        }
        subSum := prefix[n] - prefix[left+1]
        product := int64(nums[idx]) * subSum
        if product > maxProduct {
            maxProduct = product
        }
    }
    
    return int(maxProduct % int64(MOD))
}

Explanation: The Go version mirrors the Python logic but uses int64 for intermediate calculations to prevent overflow. Slices and their lengths replace stack operations.

Worked Examples

Example: nums = [1,2,3,2]

Prefix sums: [0,1,3,6,8]

Stack iteration:

  • i=0: stack=[0]
  • i=1: stack=[0,1]
  • i=2: stack=[0,1,2]
  • i=3: nums[2]=3 > 2 → pop 2: left=1, sum=prefix[3]-prefix[2]=6-3=3 → product=3_3=9

nums[1]=2 ≤ 2 → pop 1: left=0, sum=prefix[3]-prefix[1]=6-1=5 → product=2_5=10

stack=[0,3]

  • End: pop 3: left=0, sum=prefix[4]-prefix[1]=8-1=7 → product=2*7=14 (maximum)
  • pop 0: left=-1, sum=prefix[4]-prefix[0]=8-0=8 → product=1*8=8

Maximum min-product = 14

Similar step-through applies to other examples.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is pushed and popped from the stack at most once. Prefix sum computation is O(n).
Space O(n) Stack can hold up to n elements. Prefix sum array of size n+1.

The linear time arises because the monotonic stack ensures each element is considered only when popped. Prefix sums allow O(1) sum queries for subarrays.

Test Cases

# Basic examples
assert Solution().maxSumMinProduct([1,2,3,2]) == 14  # Example 1
assert Solution().maxSumMinProduct([2,3,3,1,2]) == 18  # Example 2
assert Solution().maxSumMinProduct([3,1,5,6,4,2]) == 60