Skip to main content
Talentd

Maximum Subarray Min-Product - Solution & Explanation

MediumArrayStackMonotonic StackPrefix Sum18 min readAsked at: Amazon, Uber, Google
Practice this problem

Problem Statement

The min-product of an array is equal to the minimum value in the array multiplied by the array's sum.

  • For example, the array [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 <= 105
  • 1 <= nums[i] <= 107

Approach Overview

Problem 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 1: Monotonic Stack with Prefix Sum

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Monotonic Stack + Prefix Sum

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Monotonic Stack with Prefix Sum

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.

Monotonic Stack + Prefix Sum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray EnumerationO(n^2)O(1)Useful for understanding the min-product definition or validating logic on small arrays.
Monotonic Stack with Prefix SumO(n)O(n)Best general solution for large inputs. Efficiently finds boundaries where each element is the minimum.

Video Solution

Maximum Subarray Min-Product - Monotonic Increasing Stack - Leetcode 1856 - Python • NeetCode • 40,545 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Subarray Min-Product easy or hard?
Maximum Subarray Min-Product is typically rated Medium difficulty on LeetCode. The challenge comes from recognizing that each element should be treated as the minimum of a range and then computing that range efficiently with a monotonic stack.
Maximum Subarray Min-Product Python/Java solution
Most implementations follow the same pattern: build a prefix sum array, iterate through the numbers while maintaining a monotonic stack, and compute min-products whenever an element's boundary is determined. The logic translates cleanly to Python, Java, C++, JavaScript, and other languages because it relies on simple array operations and stack pushes/pops.
How to solve Maximum Subarray Min-Product in O(n)?
Compute prefix sums to get subarray sums in constant time. Use a monotonic increasing stack to find the nearest smaller element on the left and right of each index. These boundaries define the largest subarray where the current element is the minimum. Multiply that element by the subarray sum obtained from the prefix array and track the maximum result.
What is the best approach for Maximum Subarray Min-Product?
The optimal approach uses a monotonic increasing stack combined with a prefix sum array. The stack finds the previous and next smaller element for each index, which determines the maximum subarray where that element is the minimum. Prefix sums allow constant-time computation of the subarray sum. This produces an overall O(n) time and O(n) space solution.
Is Maximum Subarray Min-Product asked at Google/Amazon/Meta?
Problems involving monotonic stacks and subarray range calculations frequently appear in interviews at companies like Amazon, Google, and Meta. Variants such as Largest Rectangle in Histogram and Sum of Subarray Minimums use the same pattern of computing boundaries with a stack.
What data structure is used in Maximum Subarray Min-Product?
The key data structure is a monotonic stack that keeps indices in increasing order of values. This structure efficiently identifies the nearest smaller element on both sides of each index. A prefix sum array is also used to compute subarray sums quickly.
What is the time complexity of Maximum Subarray Min-Product?
The optimal solution runs in O(n) time because each element is pushed to and popped from the monotonic stack at most once. Prefix sum preprocessing also takes O(n). Brute force approaches that evaluate every subarray require O(n^2) time.

Ready to solve this problem?

Practice Maximum Subarray Min-Product with our built-in code editor and test cases.

Practice on FleetCode
Previous

Subarray With Elements Greater Than Varying Threshold