Monotonic Stack — Identify Pattern
Introduction
A monotonic stack is a stack whose elements are monotonically increasing or decreasing. It contains all qualities that a typical stack has and its elements are all monotonic decreasing or increasing.
Below are the features of a monotonic stack:
- It is a range of queries in an array situation
- The minima/maxima elements
- When an element is popped from the monotonic stack, it will never be utilised again.
The monotonic stack problem is mainly the previous/next smaller/larger problem. It maintains monotonicity while popping elements when a new item is pushed into the stack.
A monotonic stack looks like the below:
Basic pseudo-code of the monotonic stack:
Concept of the monotonic stack:
Keep on pushing the elements in the stack until it is on an element that is smaller than the stack’s top and when it reaches such a number, it keeps on popping the stack till the point where it is either empty or its top is smaller than its current element. Therefore all the elements in the stack are in increasing order from bottom to top.
Code Example
Convert the below array into a monotonic stack:
nums = [2, 3, 7, 11, 5, 17, 19]Solution:
def monotonicStack(nums):
n = len(nums)
stack = []
for i in range(n):
while len(stack) > 0 and stack[-1] >= nums[i]:
stack.pop()
stack.append(nums[i])
return stackif __name__ == '__main__':
result = monotonicStack(nums)
print(result)
Output as a monotonic stack:
[2, 3, 5, 17, 19]Monotonicity of a Function
A function is called monotonic if it is either increasing or decreasing in its entire domain.
A real-world example of the monotonic function:
- The age of a living being is a monotonic increasing function in time. And the time left in life is a monotonic decreasing function in time.
Monotonically increasing functions:
If x1 < x2 and f(x1) < f(x2) then function is called as increasing function.
Monotonically decreasing functions:
If x1 < x2 and f(x1) > f(x2) then function is called as decreasing function.
Monotonic Stack Related Problem & Solution
Below is the list of problems related to the monotonic stack.
Next Greater Element
Get the next greater element for every array element.
Example:
Input: nums = [2, 7, 3, 5, 4, 6, 8]
Output: [7, 8, 5, 6, 6, 8, -1]Solution:
def getNextGreaterElements(nums):
n = len(nums)
stack = []
result = [-1] * n
for i in range(n):
while len(stack) > 0 and nums[stack[-1]] < nums[i]:
result[stack[-1]] = nums[i]
stack.pop()
stack.append(i)
return result
getNextGreaterElements(nums)Next Greater Element I
The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.
You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.
For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.
Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
Solution
class Solution(object):
def nextGreaterElement(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
stack = []
d = {}
for i in range(len(nums2)):
d[nums2[i]] = -1
for i in range(len(nums2)):
while len(stack) > 0 and nums2[i] > stack[-1]:
item = stack.pop()
d[item] = nums2[i]
stack.append(nums2[i])
for i in range(len(nums1)):
nums1[i] = d[nums1[i]]
return nums1Next Greater Element II
Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.
The next greater number of a number x is the first greater number to its traversing order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 this number.
Input: nums = [1,2,1]
Output: [2,-1,2]Explanation: The first 1's next greater number is 2;
The number 2 can't find next greater number.
The second 1's next greater number needs to search circularly, which is also 2.
Solution
class Solution(object):
def nextGreaterElements(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
n = len(nums)
stack = []
result = [-1] * n
for i in range(2*n-1):
index = i % n
while stack and stack[-1][1] < nums[index]:
resIndex, _ = stack.pop()
result[resIndex] = nums[index]
stack.append([index, nums[index]])
return resultSteps to Make Array Non-decreasing
You are given a 0-indexed integer array nums. In one step, remove all elements nums[i] where nums[i - 1] > nums[i] for all 0 < i < nums.length.
Return the number of steps performed until nums becomes a non-decreasing array.
Input: nums = [5,3,4,4,7,3,6,11,8,5,11]
Output: 3Explanation: The following are the steps performed:
- Step 1: [5,3,4,4,7,3,6,11,8,5,11] becomes [5,4,4,7,6,11,11]
- Step 2: [5,4,4,7,6,11,11] becomes [5,4,7,11,11]
- Step 3: [5,4,7,11,11] becomes [5,7,11,11]
[5,7,11,11] is a non-decreasing array. Therefore, we return 3.
Solution
class Solution(object):
def totalSteps(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
dp = [0] * n
res = 0
stack = []
for i in range(n-1, -1, -1):
while stack and nums[i] > nums[stack[-1]]:
dp[i] = max(dp[i] + 1, dp[stack.pop()])
res = max(res, dp[i])
stack.append(i)
return resTrapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.Solution
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
stack = []
total = 0
for i in range(len(height)):
while len(stack) > 0 and height[stack[-1]] < height[i]:
poppedIdx = stack.pop()
if len(stack) == 0:
break
heightVal = min(height[stack[-1]], height[i]) - height[poppedIdx]
length = i - stack[-1] - 1
total += heightVal * length
stack.append(i)
return totalLargest Rectangle in Histogram
Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.Solution
class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
maxArea = 0
stack = []
start = 0
for i, h in enumerate(heights):
start = i
while stack and stack[-1][1] > h:
index, height = stack.pop()
maxArea = max(maxArea, height * (i - index))
start = index
stack.append((start, h))
for i, h in stack:
maxArea = max(maxArea, h * (len(heights) -i))
return maxAreaRemove Duplicate Letters
Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Input: s = "bcabc"
Output: "abc"Solution
class Solution(object):
def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""
d = {char: indx for indx, char in enumerate(s)}
res = []
for indx, char in enumerate(s):
if char not in res:
while res and indx < d[res[-1]] and char < res[-1]:
res.pop()
res.append(char)
return "".join(res)Remove K Digits
Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.Solution
class Solution(object):
def removeKdigits(self, num, k):
"""
:type num: str
:type k: int
:rtype: str
"""
num=list(num)
stack,i=[num[0]],1
while i<len(num):
while stack and k>0 and num[i]<stack[-1]:
stack.pop()
k-=1
stack.append(num[i])
i+=1
while k>0:
stack.pop()
k-=1
stack="".join(stack)
return stack.lstrip("0") if stack!="" and int(stack)!=0 else "0"132 Pattern
Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].
Return true if there is a 132 pattern in nums, otherwise, return false.
Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.solution
class Solution(object):
def find132pattern(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if len(nums) < 3:
return False
right = float("-inf")
stack = []
for i in range(len(nums)-1, -1, -1):
if nums[i] < right:
return True
else:
while stack and stack[-1] < nums[i]:
right = stack.pop()
stack.append(nums[i])
return FalseDaily Temperatures
Given an array of integers temperatures represents the daily temperatures, returns an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]Solution
class Solution(object):
def dailyTemperatures(self, temperatures):
"""
:type temperatures: List[int]
:rtype: List[int]
"""
# Monotonic Stack
n = len(temperatures)
stack = []
result = [0] * n
for i in range(n-1, -1, -1):
while stack and temperatures[i] >= stack[-1][0]:
stack.pop(-1)
if len(stack) == 0:
result[i] = 0
else:
result[i] = stack[-1][1] - i
stack.append((temperatures[i], i))
return resultOnline Stock Span
Design an algorithm that collects daily price quotes for some stock and returns the span of that stock’s price for the current day.
The span of the stock’s price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the stock price was less than or equal to today’s price.
- For example, if the price of a stock over the next
7days were[100,80,60,70,60,75,85], then the stock spans would be[1,1,1,2,1,4,6].
Implement the StockSpanner class:
StockSpanner()Initializes the object of the class.int next(int price)Returns the span of the stock's price given that today's price isprice.
Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]Solution
class StockSpanner(object):def __init__(self):
self.stack = []def next(self, price):
"""
:type price: int
:rtype: int
"""
span = 1
if len(self.stack) == 0:
self.stack.append([price, span])
return 1
while self.stack and self.stack[-1][0] <= price:
span += self.stack[-1][1]
self.stack.pop()
self.stack.append([price, span])
return span# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)
Sum of Subarray Minimums
Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 109 + 7.
Input: arr = [3,1,2,4]
Output: 17
Explanation:
Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
Sum is 17.Solution
class Solution(object):
def sumSubarrayMins(self, arr):
"""
:type arr: List[int]
:rtype: int
"""
su = 0
n = len(arr)
arr.append(0)
stack = [-1]
for i, num in enumerate(arr):
while stack and arr[stack[-1]] > num: # (i)
idx = stack.pop()
su += arr[idx] * (i - idx) * (idx - stack[-1])
stack.append(i)
return su % (10**9 + 7)Smallest Subsequence of Distinct Characters
Given a string s, return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once.
Input: s = "bcabc"
Output: "abc"Solution
class Solution(object):
def smallestSubsequence(self, s):
"""
:type s: str
:rtype: str
"""
stack = []
d = {}
for i in range(len(s)):
d[s[i]] = i
for i in range(len(s)):
if s[i] not in stack:
while stack and i < d[stack[-1]] and ord(s[i]) < ord(stack[-1]):
stack.pop()
stack.append(s[i])
return (''.join(stack))Final Prices With a Special Discount in a Shop
Given the array prices where prices[i] is the price of the ith item in a shop. There is a special discount for items in the shop if you buy the ith item, then you will receive a discount equivalent to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i], otherwise, you will not receive any discount at all.
Return an array where the ith element is the final price you will pay for the ith item of the shop considering the special discount.
Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]
Explanation:
For item 0 with price[0]=8 you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is 8 - 4 = 4.
For item 1 with price[1]=4 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 4 - 2 = 2.
For item 2 with price[2]=6 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 6 - 2 = 4.
For items 3 and 4 you will not receive any discount at all.Solution
class Solution(object):
def finalPrices(self, prices):
"""
:type prices: List[int]
:rtype: List[int]
"""
stack = []
l = len(prices)
for i in range(0, l):
while stack and prices[stack[-1]] >= prices[i]:
p = stack.pop()
prices[p] -= prices[i]
stack.append(i)
return pricesSteps to Make Array Non-decreasing
You are given a 0-indexed integer array nums. In one step, remove all elements nums[i] where nums[i - 1] > nums[i] for all 0 < i < nums.length.
Return the number of steps performed until nums becomes a non-decreasing array.
Input: nums = [5,3,4,4,7,3,6,11,8,5,11]
Output: 3
Explanation: The following are the steps performed:
- Step 1: [5,3,4,4,7,3,6,11,8,5,11] becomes [5,4,4,7,6,11,11]
- Step 2: [5,4,4,7,6,11,11] becomes [5,4,7,11,11]
- Step 3: [5,4,7,11,11] becomes [5,7,11,11]
[5,7,11,11] is a non-decreasing array. Therefore, we return 3.Solution
class Solution(object):
def totalSteps(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
dp = [0] * n
res = 0
stack = []
for i in range(n-1, -1, -1):
while stack and nums[i] > nums[stack[-1]]:
dp[i] = max(dp[i] + 1, dp[stack.pop()])
res = max(res, dp[i])
stack.append(i)
return resMax Chunks To Make Sorted
You are given an integer array arr of length n that represents a permutation of the integers in the range [0, n - 1].
We split arr into some number of chunks (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array.
Return the largest number of chunks we can make to sort the array.
Input: arr = [4,3,2,1,0]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.Solution
class Solution(object):
def maxChunksToSorted(self, arr):
"""
:type arr: List[int]
:rtype: int
"""
stack=[]
stack.append(arr[0])
top=1
largest=0
for i in range(1,len(arr)): #scan left to right from 1 to l-1
if(arr[i]>stack[top-1]): # if element on top of stack < arr[i] push element in stack and increment top of stack as well
stack.append(arr[i])
top+=1else:
while((top)>0 and arr[i]<stack[top-1]): #if top of stack > arr[i], run loop till stack >arr[i]
if(stack[top-1]>largest): #keeping track of largest element we pop so we can replace pop elements with single largest element
largest=stack[top-1]
stack.pop() #poping element from stack while stack[top-1]>arr[i] and top>0
top-=1
stack.append(largest) #pushing largest element in stack
top+=1
return len(stack)
Time Complexity
The time complexity of a monotonic stack-based solution is O(n) because while loop simply pops out stack elements one by one and there can’t be more than n elements pushed inside the stack as every element is pushed once. Therefore nested while loop will also not execute more than n times. The inner loop will not be counted as a nested loop until its covers n elements.
Conclusion
A monotonic stack is a particular form of the stack inside which all items are sorted in either ascending or descending order
