LeetCode Solutions Blog

Maximum Subarray Min-Product

Number: 1985

Difficulty: Medium

Paid? No

Companies: Amazon, Uber

Problem Description

Given an array of integers, the task is to find the non-empty subarray with the maximum min-product. The min-product of a subarray is defined as the minimum value in that subarray multiplied by the sum of all its elements. Since the answer may be large, return it modulo 10^9 + 7.

Key Insights

The candidate subarray for each element is the maximal subarray in which that element is the minimum.
Use a monotonic stack to efficiently determine the left and right boundaries where each element remains the minimum.
Precompute prefix sums to quickly calculate the sum of any subarray.
Process each element by computing the candidate subarray sum using its boundaries and then determine the min-product.
Use modulo arithmetic at the end to handle large numbers.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

We first compute a prefix sum array to allow O(1) subarray sum queries. For each element in the array, we determine the indices of the first smaller element to the left and to the right using a monotonic increasing stack. These boundaries indicate the range in which the current element is the minimum. Using these boundaries, we compute the subarray sum and then the min-product (current element * subarray sum). Track the maximum min-product obtained and return it modulo 10^9 + 7.

Code Solutions

# Python implementation with detailed comments

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        
        # Compute prefix sum array where prefix[i+1] = sum(nums[0] .. nums[i])
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i+1] = prefix[i] + nums[i]
        
        # Arrays to store the first index to the left/right of i where nums[j] < nums[i]
        left = [-1] * n  # default: no smaller element to the left, use -1 as sentinel
        right = [n] * n  # default: no smaller element to the right, use n as sentinel

        # Monotonic stack for left boundary
        stack = []
        for i in range(n):
            # Pop until the current element is greater than the stack's top element
            while stack and nums[stack[-1]] >= nums[i]:
                stack.pop()
            # If stack not empty, the top is the previous smaller element's index
            if stack:
                left[i] = stack[-1]
            # Push current index into the stack
            stack.append(i)

        # Clear stack for the right boundary computation
        stack = []
        for i in range(n-1, -1, -1):
            # Pop until the current element is strictly less than the top element of stack
            while stack and nums[stack[-1]] >= nums[i]:
                stack.pop()
            # If stack not empty, then the top element is the first smaller element on the right
            if stack:
                right[i] = stack[-1]
            stack.append(i)

        # Calculate the maximum min-product from each candidate subarray
        max_product = 0
        for i in range(n):
            # Compute the subarray sum using the prefix sum array
            total = prefix[right[i]] - prefix[left[i] + 1]
            max_product = max(max_product, nums[i] * total)

        return max_product % MOD