After solved 1000 medium leetcode found thes patterns — Mono-Stack

LORY
4 min readMar 19, 2022

Continue the leetcode pattern series : DFS, BFS and DP , BackTracking . This article I summary and explain with some high ranking problems for 1 more classic pattern — monolithic stack .

Lets get into it .

Try to identify the pattern below for stack1 and stack2 .

index :  0  1  2  3  4  5  6  7
Array : [3, 7, 1, 4, 7, 2, 9, 8]
stack1: [3]:index=0
[3,7]:index=1
[1]:index=2
[1,4]:index=3
[1,4,7]:index=4
[1,2]:index=5
[1,2,9]:index=6
[1,2,8]:index=7
Array : [3, 7, 1, 4, 7, 2, 9, 8]
stack2: [3]:index=0
[7]:index=1
[7,1]:index=2
[7,4]:index=3
[7,7]:index=4
[7,7,2]:index=5
[9]:index=6
[9,8]:index=7

Yes, you got it .

This is the idea of monolithic stack . stack1 is “increasing stack” — [elements before self , from biggest to smallest] ≤ self ; stack2 is “decreasing stack” — [elements before self from smallest to biggest] ≥ self

Implementation of a decreasing stack .

stack = []
for i in range(len(arr)): # loop from last to first
# change to >= for increasing stack
while stack and stack[-1] <= arr[i]:
val = stack.pop()
if condition(val):
update_result(val)
stack.append(arr[i])

Now lets see some leetcode problems .

503. Next Greater Element II

Thought process. This is classic mono-stack problem. to know the “next greater element” , need to loop from last element to first, and using a “decreasing stack” to track the “next greater” element .

def nextGreaterElements(self, nums: List[int]) -> List[int]:
"""
1 2 3 4 3 1 2 3 4 3
[3]
[4]
[3,4]
[2,3,4]
[1,2,3,4]
[4]
[4,4]
[3,4,4]
"""
stack = [] # increasing stack
res={i:-1 for i in range(len(nums))}
nums2 = nums*2 # handle circular
for i in range(len(nums2)-1, -1, -1):
n = nums2[i]
while stack and nums2[stack[-1]] <= n:
stack.pop()
if stack:
res[i]=nums2[stack[-1]]
stack.append(i)

return [n for idx, n in sorted(res.items(), key=lambda x:x[0]) if idx < len(nums)]

Or, you could also loop from first element, use an increasing stack . and update result[stack.pop()]=current_element

def nextGreaterElements(self, nums: List[int]) -> List[int]:
"""
array: a1, a2, a3, ...ai...an
|
stack: a1>a2>a3 <= ai ?
yes, update res[a3] = ai
no, stack: a1>a2>ai,.. continue until the end
...
"""

stack = []
res={}
nums2 = nums*2 # handle circular
for i, n in enumerate(nums2):
while stack and nums2[stack[-1]] < n:
res[stack.pop()]=n
stack.append(i)

while stack :
res[stack.pop()]=-1
return [n for idx, n in sorted(res.items(), key=lambda x:x[0] if idx < len(nums)]

901. Online Stock Span

Thought process . Since the rule to “span” previous element is when value<self . so we need a decreasing stack to track the [element before self]>self, while popping stack, res[current element] = res[top element on stack]+1, here we also need use res[] to track the answer for each element .

Explained with an example in comments .

class StockSpanner:def __init__(self):
self.stack = [] # stack to store # of elements <= self, top element is the smallest
def next(self, price: int) -> int:
"""
100 80 60 70 60 75 85
stack : 100:1 80:1 60:1 70:2 60:1 75:4 85:6
100:1 80:1 80:1 70:2 80:1 100:1
100:1 100:1 80:1 100:1
100:1
"""
res = 1
while self.stack and self.stack[-1][0] <= price:
res += self.stack.pop()[1]
self.stack.append([price, res])
return res

Last one.

316. Remove Duplicate Letters

Thought process explained in code comments. the core idea is maintein a increasing stack + greedy thinking (check if there are more char left in char counter)

def removeDuplicateLetters(self, s: str) -> str:
"""
stack[] : increasing mono-stack
wc : a char counter to track <char_in_s : count>
for each char in s
Case 1: stack empty : add in stack
Case 2: stack [-1] < current, if already in stack, no need else add in
Case 3: stack [-1] > current, pop stack if there is more <current> left in wc
"""
wc = collections.Counter(s)
arr = []
for c in s:
if not arr:
arr.append(c)
wc[c]-=1
continue
if arr[-1] < c:
if c not in arr:
arr.append(c)
elif arr[-1] > c:
if c not in arr:
while arr and arr[-1] >= c and wc[arr[-1]] > 0:
arr.pop()
arr.append(c)
wc[c]-=1
return ''.join(arr)

More mono stack problems for practice .

402. Remove K Digits .

456. 132 Pattern

581. Shortest Unsorted Continuous Subarray

946. Validate Stack Sequences 962. Maximum Width Ramp

Other stack related problems but not mono-stack

These are good “start” problems to understand the idea of stack itself .

150. Evaluate Reverse Polish Notation (This is basic classic stack problem, beginner can start here)

227. Basic Calculator II (This is another basic classic stack problem, beginner can start here)

71. Simplify Path (Simple)

331. Verify Preorder Serialization of a Binary Tree

Conclusion

Mono-stack is not easy to think of in first place. when there is a problem need us to have an array to track all previous or next “greater” or “smaller” elements and maintein a “from smallest to largest” or “largest to smallest” sequence , this is more likely mono-stack problem.

Thanks for reading , happy leetcoding !

--

--

LORY

A channel which focusing on developer growth and self improvement