Watch 10 video solutions for Maximum Subarray Min-Product, a medium level problem involving Array, Stack, Monotonic Stack. This walkthrough by NeetCode has 39,517 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
The min-product of an array is equal to the minimum value in the array multiplied by the array's sum.
[3,2,5] (minimum value is 2) has a min-product of 2 * (3+2+5) = 2 * 10 = 20.Given an array of integers nums, return the maximum min-product of any non-empty subarray of nums. Since the answer may be large, return it modulo 109 + 7.
Note that the min-product should be maximized before performing the modulo operation. Testcases are generated such that the maximum min-product without modulo will fit in a 64-bit signed integer.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1,2,3,2] Output: 14 Explanation: The maximum min-product is achieved with the subarray [2,3,2] (minimum value is 2). 2 * (2+3+2) = 2 * 7 = 14.
Example 2:
Input: nums = [2,3,3,1,2] Output: 18 Explanation: The maximum min-product is achieved with the subarray [3,3] (minimum value is 3). 3 * (3+3) = 3 * 6 = 18.
Example 3:
Input: nums = [3,1,5,6,4,2] Output: 60 Explanation: The maximum min-product is achieved with the subarray [5,6,4] (minimum value is 4). 4 * (5+6+4) = 4 * 15 = 60.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 107Problem Overview: You are given an integer array and must compute the maximum min-product among all subarrays. The min-product of a subarray equals the minimum element in that subarray multiplied by the sum of that subarray. The challenge is evaluating this efficiently without enumerating every possible subarray.
Approach 1: Brute Force Enumeration (O(n^2) time, O(1) space)
Start each subarray at index i and expand it to the right while tracking the current minimum and running sum. For every extension j, update the minimum value and compute min * sum. This approach checks all O(n^2) subarrays. Although the logic is straightforward, it becomes slow for large inputs because every subarray must be evaluated individually. This approach mainly helps verify correctness before optimizing.
Approach 2: Monotonic Stack with Prefix Sum (O(n) time, O(n) space)
The optimal solution treats each element as the minimum of some subarray and determines the largest range where it remains the smallest value. A monotonic stack helps find the previous and next smaller elements for every index. These boundaries define the widest subarray where the current element is the minimum.
Once the boundaries are known, compute the subarray sum in constant time using a prefix sum array. If an element at index i is the minimum between indices left+1 and right-1, the subarray sum becomes prefix[right] - prefix[left + 1]. Multiply this sum by nums[i] to get the min-product contributed by that element. Track the maximum across all indices.
This works because every subarray has exactly one element acting as its minimum that defines its valid expansion range. The stack ensures each index is pushed and popped once, giving linear complexity. The combination of array traversal, prefix sums, and monotonic boundaries removes the need to evaluate each subarray explicitly.
Recommended for interviews: Interviewers expect the monotonic stack + prefix sum approach. Brute force demonstrates the core observation about minimum values inside subarrays, but the optimal method shows you understand how to convert that observation into an O(n) solution using stack-based boundary detection and constant-time range sums.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Enumeration | O(n^2) | O(1) | Useful for understanding the min-product definition or validating logic on small arrays. |
| Monotonic Stack with Prefix Sum | O(n) | O(n) | Best general solution for large inputs. Efficiently finds boundaries where each element is the minimum. |