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.
This approach leverages a monotonic stack to find the nearest smaller left and right elements for each element in the array, thus identifying the bounds of subarray where an element is minimum. We compute prefix sums to efficiently calculate the sum of any subarray. For each element as the potential minimum, compute its min-product, track the maximum possible, and return it modulo 10^9 + 7.
This C code uses arrays to maintain the nearest smaller elements to the left and right of each element. A prefix sum array helps calculate the sum of subarrays efficiently. The core logic is implemented using stacks, and we iterate through the list twice: once for the left boundaries and once for the right, ensuring we can determine subarray limits in O(n) time.
Time Complexity: O(n) - We iterate over the array elements a constant number of times.
Space Complexity: O(n) - Due to additional data structures like left, right, and prefix sum arrays.
We can enumerate each element nums[i] as the minimum value of the subarray, and find the left and right boundaries left[i] and right[i] of the subarray. Where left[i] represents the first position strictly less than nums[i] on the left side of i, and right[i] represents the first position less than or equal to nums[i] on the right side of i.
To conveniently calculate the sum of the subarray, we can preprocess the prefix sum array s, where s[i] represents the sum of the first i elements of nums.
Then the minimum product with nums[i] as the minimum value of the subarray is nums[i] times (s[right[i]] - s[left[i] + 1]). We can enumerate each element nums[i], find the minimum product with nums[i] as the minimum value of the subarray, and then take the maximum value.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Monotonic Stack with Prefix Sum | Time Complexity: O(n) - We iterate over the array elements a constant number of times. |
| Monotonic Stack + Prefix Sum | — |
| 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. |
Maximum Subarray Min-Product - Monotonic Increasing Stack - Leetcode 1856 - Python • NeetCode • 39,517 views views
Watch 9 more video solutions →Practice Maximum Subarray Min-Product with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor