chalk.
DSA

Mode

Colours

PricingSign inStart free

Index

Free, with Google

Keep going, free.

A free account opens lessons 2 and 3 of every track, 33 more lessons, and keeps your progress and review cards on every device.

Start free with Google

Launch price

Open everything on chalk.

Every lesson, board, video, lab and paper, and the full review decks. Yearly is $39/year, or $19.50 for your first year with LAUNCH50, ends 1 Nov, 18:30 UTC.

See plansStart free instead

Learn / DSA

Module 09 · DSA · Four patterns the ladders lean on

The stack that stays sorted (monotonic stack and deque)

Before you start. Linked Lists, Stacks & Queues gave you the stack: a pile where only the top item can be touched, so the last thing put on is the first thing taken off. Clinic #08: Daily Temperatures (the Hinglish clinic) solved one problem with a stack kept in order. This lesson takes that one trick, names it, shows why it is fast, and finds three more problems hiding in it. The Practice Ladders is where you practise afterwards.

Lesson 69 of 74 in DSA

The rest of this lesson is part of a plan.

A plan opens every lesson, board, video, lab and paper on chalk. Yearly is $39/year, or $19.50 for your first year with LAUNCH50, ends 1 Nov, 18:30 UTC.

See plansAlready a member? Sign in

Or start free: a free account opens lessons 2 and 3 of every track.

In this lesson

  • 2006: a sensor stream and a promise of three comparisons
  • One row of numbers, and the waiting room
  • The monotonic stack, and the next greater element
  • Amortized: the inner loop looks scary, and is not
  • Flip the question: who is the previous smaller number?
  • Two walls from one stack: the largest rectangle
  • The window: a monotonic deque
  • How to tell which one you need
  • The ladder

Terms it explains: monotonic stack, next greater element, amortized, previous smaller element, sliding window maximum, monotonic deque.

Review DSA

Connects to