Your monotonic stack solution works perfectly on the examples. You submit. Wrong Answer.
The failing test case: [2, 2, 2, 2] — an array of duplicates.
What went wrong? You're double-counting subarrays because both duplicates think they're the minimum of the same subarray.
This is one of the most subtle bugs in monotonic stack problems, and it only appears when duplicates are present. Understanding how to fix it is crucial for problems like "Sum of Subarray Minimums."
This guide will teach you why duplicates break monotonic stacks, the asymmetric comparison fix, and when to use strict vs non-strict inequality.
Problem: Duplicates cause double-counting in contribution technique problems.
Solution: Use asymmetric comparison:
< or >)<= or >=)Example:
# Right boundary: strict <
while stack and arr[i] < arr[stack[-1]]:
right[stack.pop()] = i
# Left boundary: non-strict <=
while stack and arr[i] <= arr[stack[-1]]:
left[stack.pop()] = iWhy: Ensures each subarray is counted exactly once, even with duplicates.
Problem: Sum of Subarray Minimums
Array: [2, 2, 2]
Expected subarrays:
[2] → min = 2
[2] → min = 2
[2] → min = 2
[2, 2] → min = 2
[2, 2] → min = 2
[2, 2, 2] → min = 2
Sum = 2 + 2 + 2 + 2 + 2 + 2 = 12def sumSubarrayMins_wrong(arr):
"""
WRONG: Uses strict < on both sides
"""
n = len(arr)
left = [-1] * n
right = [n] * n
# Both use strict <
stack = []
for i in range(n):
while stack and arr[i] < arr[stack[-1]]: # Strict <
right[stack.pop()] = i
stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[i] < arr[stack[-1]]: # Strict <
left[stack.pop()] = i
stack.append(i)
# Calculate contributions
result = 0
for i in range(n):
count = (i - left[i]) * (right[i] - i)
result += arr[i] * count
return result
# Test
arr = [2, 2, 2]
print(sumSubarrayMins_wrong(arr))
# Output: 18 (WRONG! Expected: 12)Trace for [2, 2, 2]:
Finding right boundaries (strict <):
i=0, val=2: stack=[0]
i=1, val=2: 2 not < 2, stack=[0,1]
i=2, val=2: 2 not < 2, stack=[0,1,2]
right = [3, 3, 3] (all extend to end)
Finding left boundaries (strict <):
i=2, val=2: stack=[2]
i=1, val=2: 2 not < 2, stack=[2,1]
i=0, val=2: 2 not < 2, stack=[2,1,0]
left = [-1, -1, -1] (all extend to start)
Contributions:
i=0: count = (0-(-1)) × (3-0) = 1 × 3 = 3, contrib = 2 × 3 = 6
i=1: count = (1-(-1)) × (3-1) = 2 × 2 = 4, contrib = 2 × 4 = 8
i=2: count = (2-(-1)) × (3-2) = 3 × 1 = 3, contrib = 2 × 3 = 6
Total = 6 + 8 + 6 = 20... wait, let me recalculateActually, let me trace this more carefully:
With strict < on both sides:
All three elements think they're the minimum of [2,2,2]
i=0: left=-1, right=3, count=(0-(-1))×(3-0)=3, contrib=6
i=1: left=-1, right=3, count=(1-(-1))×(3-1)=4, contrib=8
i=2: left=-1, right=3, count=(2-(-1))×(3-2)=3, contrib=6
Total = 6 + 8 + 6 = 20 (WRONG!)The problem: Subarray [2,2] is counted by both index 0 and index 1. Subarray [2,2,2] is counted by all three indices.
Use strict inequality on ONE side, non-strict on the OTHER:
def sumSubarrayMins_correct(arr):
"""
CORRECT: Uses asymmetric comparison
"""
n = len(arr)
left = [-1] * n
right = [n] * n
# Right: strict < (pop when current is strictly smaller)
stack = []
for i in range(n):
while stack and arr[i] < arr[stack[-1]]:
right[stack.pop()] = i
stack.append(i)
# Left: non-strict <= (pop when current is smaller or equal)
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[i] <= arr[stack[-1]]:
left[stack.pop()] = i
stack.append(i)
# Calculate contributions
result = 0
for i in range(n):
count = (i - left[i]) * (right[i] - i)
result += arr[i] * count
return result
# Test
arr = [2, 2, 2]
print(sumSubarrayMins_correct(arr))
# Output: 12 ✓Trace for [2, 2, 2] with asymmetric comparison:
Finding right boundaries (strict <):
i=0, val=2: stack=[0]
i=1, val=2: 2 not < 2, stack=[0,1]
i=2, val=2: 2 not < 2, stack=[0,1,2]
right = [3, 3, 3]
Finding left boundaries (non-strict <=):
i=2, val=2: stack=[2]
i=1, val=2: 2 <= 2, pop 2, left[2]=1, stack=[1]
i=0, val=2: 2 <= 2, pop 1, left[1]=0, stack=[0]
left = [-1, 0, 1]
Contributions:
i=0: count = (0-(-1)) × (3-0) = 1 × 3 = 3, contrib = 2 × 3 = 6
Claims: [2], [2,2], [2,2,2]
i=1: count = (1-0) × (3-1) = 1 × 2 = 2, contrib = 2 × 2 = 4
Claims: [2], [2,2]
i=2: count = (2-1) × (3-2) = 1 × 1 = 1, contrib = 2 × 1 = 2
Claims: [2]
Total = 6 + 4 + 2 = 12 ✓Key insight: With asymmetric comparison:
No overlap! Each subarray is claimed by exactly one element.
For duplicates, we need a tiebreaker:
Asymmetric comparison provides the tiebreaker:
Array: [2, 2, 2]
[0 1 2]
With asymmetric comparison (strict right, non-strict left):
Element 0 (left=-1, right=3):
Owns: [0,0], [0,1], [0,2]
Subarrays: [2], [2,2], [2,2,2]
Element 1 (left=0, right=3):
Owns: [1,1], [1,2]
Subarrays: [2], [2,2]
Element 2 (left=1, right=3):
Owns: [2,2]
Subarrays: [2]
Total subarrays: 3 + 2 + 1 = 6 ✓Convention: Strict on right, non-strict on left
But you can reverse it:
# Alternative: strict left, non-strict right
# Right: non-strict >=
while stack and arr[i] >= arr[stack[-1]]:
right[stack.pop()] = i
# Left: strict >
while stack and arr[i] > arr[stack[-1]]:
left[stack.pop()] = iBoth work! Just be consistent.
Contribution technique with duplicates
Counting subarrays where element is min/max
Duplicates are possible in the input
Next greater/smaller element (not counting)
Histogram problems (area calculation)
No duplicates in the input (guaranteed)
❌ Wrong:
# Both strict
while stack and arr[i] < arr[stack[-1]]: # Right
while stack and arr[i] < arr[stack[-1]]: # Left
# Duplicates not handled!✅ Correct:
# Asymmetric
while stack and arr[i] < arr[stack[-1]]: # Right: strict
while stack and arr[i] <= arr[stack[-1]]: # Left: non-strict❌ Wrong:
# Both non-strict
while stack and arr[i] <= arr[stack[-1]]: # Right
while stack and arr[i] <= arr[stack[-1]]: # Left
# Different problem: no elements remain in stack!Result: Stack becomes empty too quickly, boundaries are wrong.
❌ Wrong:
# Sometimes strict right, sometimes strict left
# Inconsistent across different parts of code✅ Correct:
# Pick one convention and stick to it
# Strict right, non-strict left (recommended)❌ Wrong:
# "The examples work, so I don't need asymmetric comparison"
# Fails on duplicate test cases✅ Correct:
# Always use asymmetric comparison for contribution technique
# Even if examples don't have duplicates# Test 1: All same values
arr = [2, 2, 2, 2]
# Should handle gracefully
# Test 2: Pairs of duplicates
arr = [1, 1, 2, 2, 3, 3]
# Each pair should be handled correctly
# Test 3: Three duplicates
arr = [5, 5, 5]
# Edge case for asymmetric comparison
# Test 4: Duplicates at boundaries
arr = [1, 2, 2, 2, 3]
# Middle duplicates
# Test 5: Large duplicate sequence
arr = [1] * 1000
# Stress testdef sumSubarrayMins(arr):
"""
LeetCode #907: Sum of Subarray Minimums
Correct implementation with asymmetric comparison.
Time: O(n)
Space: O(n)
"""
n = len(arr)
MOD = 10**9 + 7
# Find boundaries
left = [-1] * n # Next smaller to left
right = [n] * n # Next smaller to right
# Right: strict < (current is strictly smaller)
stack = []
for i in range(n):
while stack and arr[i] < arr[stack[-1]]:
right[stack.pop()] = i
stack.append(i)
# Left: non-strict <= (current is smaller or equal)
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[i] <= arr[stack[-1]]:
left[stack.pop()] = i
stack.append(i)
# Calculate contributions
result = 0
for i in range(n):
# Count of subarrays where arr[i] is minimum
left_count = i - left[i]
right_count = right[i] - i
count = left_count * right_count
# Contribution of arr[i]
contribution = (arr[i] * count) % MOD
result = (result + contribution) % MOD
return result
# Test cases
print(sumSubarrayMins([3, 1, 2, 4])) # 17
print(sumSubarrayMins([2, 2, 2])) # 12
print(sumSubarrayMins([1, 1, 1, 1])) # 10
print(sumSubarrayMins([71, 55, 82, 55])) # 593Q: Why does asymmetric comparison prevent double-counting?
A: It creates a consistent tiebreaker. When two elements have the same value, the asymmetric rule determines which one "owns" the subarray between them.
Q: Can I use strict on left and non-strict on right instead?
A: Yes! Both conventions work. Just be consistent throughout your code.
Q: Do I always need asymmetric comparison for monotonic stacks?
A: No. Only for contribution technique problems where you're counting subarrays. For "next greater element" problems, symmetric comparison is fine.
Q: How do I remember which side should be strict?
A: Mnemonic: "Right is stRict" (both have R). Or just pick one convention and always use it.
Duplicate handling is a subtle but critical detail in monotonic stack problems.
Key principles:
The fix:
# Right: strict <
while stack and arr[i] < arr[stack[-1]]:
right[stack.pop()] = i
# Left: non-strict <=
while stack and arr[i] <= arr[stack[-1]]:
left[stack.pop()] = iWhen to use:
Master this technique, and you'll never fail on duplicate test cases again.
Next steps:
Next time you see duplicates in a contribution problem, remember: asymmetric comparison.
LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free