DSA Visualizations | Hello Interview

Monotonic Stack

A monotonic stack is a special type of stack in which all elements on the stack are sorted in either descending or ascending order. It is used to solve problems that require finding the next greater or next smaller element in an array.

A montonically decreasing stack

Problem: Next Greater Element

DESCRIPTION

Given an array of integers, find the next greater element for each element in the array. The next greater element of an element x is the first element to the right of x that is greater than x. If there is no such element, then the next greater element is -1.

Example Input: [2, 1, 3, 2, 4, 3] Output: [3, 3, 4, 4, -1, -1]

The solution iterates over each index in the input array. For each index, it checks if the element at that index is the next greater element for any previous elements in the array. In order to perform that check efficiently, we'll use a monotonic decreasing stack.

Initialization

We start by initializing our stack and our results array, with each value in the results array initialized to -1. Our stack stores the indexes of the elements in the input array that have not yet found their next greater element.


def nextGreaterElement(nums):
  n = len(nums)
  result = [-1] * n
  stack = []

  for i in range(n):
    while stack and nums[i] > nums[stack[-1]]:
      idx = stack.pop()
      result[idx] = nums[i]
    stack.append(i)

  return result

0 / 1

Iteration

We then iterate over the input array. To check if the current element nums[i] is the next greater element for any of the previous elements in the array, we compare the current element with the element at the index at the top of the stack nums[stack[-1]].

If the stack is empty, or if nums[i] is less than nums[stack[-1]], we push the current index onto the stack.


def nextGreaterElement(nums):
  n = len(nums)
  result = [-1] * n
  stack = []

  for i in range(n):
    while stack and nums[i] > nums[stack[-1]]:
      idx = stack.pop()
      result[idx] = nums[i]
    stack.append(i)

  return result

0 / 4

Pushing indexes 0 and 1 onto the stack

Recall that the stack contains the indexes of the elements in the input array that have not yet found their next greater element. At this point, we can see that the values at each of the indexes on the stack (i.e. nums[0] and nums[1]) are monotonically decreasing. This property allows us to check if nums[i] is the next greater element for any of the indexes on the stack efficiently.

If nums[i] is smaller than nums[stack[-1]], because the stack is monotonically decreasing, we also know that nums[i] is not the next greater element for any of the other indexes on the stack as well, so we can push index i onto the stack.

Processing Next Greater Elements

If the nums[i] is greater than nums[stack[-1]], then we have found the next greater element for the index stack[-1]. So we pop that index from the stack (idx), and update results[idx] to be nums[i].

Because it is still possible for nums[i] to be the next greatest element for the remaining indexes on the stack, we have to repeat this processing operation until nums[i] is not greater than nums[stack[-1]], at which point we have finished processing all the indexes for which nums[i] is the next greatest element, so we push i onto the stack.


def nextGreaterElement(nums):
  n = len(nums)
  result = [-1] * n
  stack = []

  for i in range(n):
    while stack and nums[i] > nums[stack[-1]]:
      idx = stack.pop()
      result[idx] = nums[i]
    stack.append(i)

  return result

0 / 4

Processing indexes for which 3 is the next greatest element

Popping all the elements that are smaller than nums[i] from the stack before pushing i ensures that the stack stays monotonically decreasing.

This process continues until the end of the input array, at which point the results array contains the next greater element for each element in the input array, or -1 if there is no such element.

Solution


def nextGreaterElement(nums):
  n = len(nums)
  result = [-1] * n
  stack = []

  for i in range(n):
    while stack and nums[i] > nums[stack[-1]]:
      idx = stack.pop()
      result[idx] = nums[i]
    stack.append(i)

  return result

0 / 18

Next Smaller Element

Following the same pattern, we can use a monotonically increasing stack to solve problems that require finding the next smaller element in an array.


def nextSmallerElement(nums):
  n = len(nums)
  result = [-1] * n
  stack = []

  for i in range(n):
    while stack and nums[i] < nums[stack[-1]]:
      idx = stack.pop()
      result[idx] = nums[i]
    stack.append(i)

  return result

0 / 17

Practice Problems

For more practice with problems that use a monotonic stack, try:

Daily Temperatures Leetcode | Solution

Largest Rectangle in Histogram Leetcode | Solution

Buildings with an Ocean View Leetcode

Next: Daily Temperatures

Your account is free and you can post anonymously if you choose.

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Longest Valid Parentheses

Daily Temperatures

Monotonic Stack

A montonically decreasing stack

Problem: Next Greater Element

DESCRIPTION

Example Input: [2, 1, 3, 2, 4, 3] Output: [3, 3, 4, 4, -1, -1]

Initialization


def nextGreaterElement(nums):
  n = len(nums)
  result = [-1] * n
  stack = []

  for i in range(n):
    while stack and nums[i] > nums[stack[-1]]:
      idx = stack.pop()
      result[idx] = nums[i]
    stack.append(i)

  return result

0 / 1

Iteration

If the stack is empty, or if nums[i] is less than nums[stack[-1]], we push the current index onto the stack.


def nextGreaterElement(nums):
  n = len(nums)
  result = [-1] * n
  stack = []

  for i in range(n):
    while stack and nums[i] > nums[stack[-1]]:
      idx = stack.pop()
      result[idx] = nums[i]
    stack.append(i)

  return result

0 / 4

Pushing indexes 0 and 1 onto the stack

Processing Next Greater Elements

If the nums[i] is greater than nums[stack[-1]], then we have found the next greater element for the index stack[-1]. So we pop that index from the stack (idx), and update results[idx] to be nums[i].


def nextGreaterElement(nums):
  n = len(nums)
  result = [-1] * n
  stack = []

  for i in range(n):
    while stack and nums[i] > nums[stack[-1]]:
      idx = stack.pop()
      result[idx] = nums[i]
    stack.append(i)

  return result

0 / 4

Processing indexes for which 3 is the next greatest element

Popping all the elements that are smaller than nums[i] from the stack before pushing i ensures that the stack stays monotonically decreasing.

This process continues until the end of the input array, at which point the results array contains the next greater element for each element in the input array, or -1 if there is no such element.

Solution


def nextGreaterElement(nums):
  n = len(nums)
  result = [-1] * n
  stack = []

  for i in range(n):
    while stack and nums[i] > nums[stack[-1]]:
      idx = stack.pop()
      result[idx] = nums[i]
    stack.append(i)

  return result

0 / 18

Next Smaller Element

Following the same pattern, we can use a monotonically increasing stack to solve problems that require finding the next smaller element in an array.


def nextSmallerElement(nums):
  n = len(nums)
  result = [-1] * n
  stack = []

  for i in range(n):
    while stack and nums[i] < nums[stack[-1]]:
      idx = stack.pop()
      result[idx] = nums[i]
    stack.append(i)

  return result

0 / 17

Practice Problems

For more practice with problems that use a monotonic stack, try:

Daily Temperatures Leetcode | Solution

Largest Rectangle in Histogram Leetcode | Solution

Buildings with an Ocean View Leetcode

Next: Daily Temperatures

Your account is free and you can post anonymously if you choose.

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103