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

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  7Array : [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=7Array : [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 circularfor 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 smallestdef 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 .

456. 132 Pattern

581. Shortest Unsorted Continuous Subarray

## 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 !

--

--

A channel which focusing on developer growth and self improvement