This is part of a series where I break down coding concepts I understand when reading about them but struggle to reuse when I actually need them. Not tutorials. Personal learning journeys that break down the "why does this actually work" part.
The problem that tripped me up
LeetCode 1856: Maximum Subarray Min-Product. The formula is straightforward. For any subarray, multiply the minimum element by the sum of the subarray. Find the maximum across all possible subarrays.
I could see the O(n^2) solution clearly. Try every subarray, track the running min and running sum, update the max. But dropping to O(n)? That's where I got stuck.
Where my intuition went wrong
My first instinct was a sliding window approach. Add an element to the range, check if it improves the answer, otherwise store the max and reset. It felt right because you're building ranges and checking them.
But here's why it fails: the decision to "keep going or reset" depends on both the sum AND the minimum changing at the same time. Adding a large number helps the sum but might not help if the min stays low. Adding a small number hurts the min but you don't know yet whether the sum makes up for it. There's no clean greedy condition to check.
I was stuck because I was asking the wrong question.
The reframe that made it click
Instead of asking "what's the best range?", flip it:
For each element, what's the widest subarray where THAT element is the minimum?
Why does this cover every possible answer? Because whatever the optimal subarray is, it has some minimum element. That minimum is one of the values in the array. So if you check every element as a potential minimum and find its best subarray, you're guaranteed to find the answer.
This changes the problem from "search all subarrays" to "for each element, find its boundaries." And finding boundaries is exactly what a monotonic stack does.
to help people get better at problems like these. If you want more breakdowns like this, check it out.
SOCIAL SHARE CARD GENERATOR