DSA Notes

Data Structures

Stack

Last in, first out: the newest item is the first to leave.

The idea

A stack only lets you touch its top: push adds an item there, pop removes it, top reads it. Each operation is O(1).

It fits any problem where the most recent unfinished thing must be handled first: matching brackets, evaluating expressions, undoing steps, depth-first search.

A monotonic stack keeps its values in increasing (or decreasing) order by popping everything the new item makes useless. Every item is pushed once and popped at most once, so a whole scan costs O(n). It answers “nearest smaller / greater element” questions.

Sample problem

739. Daily Temperatures ↗ Medium

Given the temperature of each day, return for every day how many days you have to wait for a warmer one, or 0 if none comes.

temperatures = [73,74,75,71,69,72,76,73]
output       = [1,1,4,2,1,1,0,0]

Why the solution works

Checking every later day for each day is O(n²). Instead, keep the days that are still waiting on a stack.

When a new day arrives, it answers every waiting day that is colder than it. Those days are exactly the ones on top of the stack, because a colder day that arrived after a warmer one sits above it. Pop them, record the wait, then push the new day.

The stack therefore always holds temperatures in falling order: a monotonic stack. Last in, first out is what makes “the most recent colder days” available at the top.

Complexity: O(n) time: each day is pushed and popped at most once. O(n) memory.

Watch out

  • Calling top() or pop() on an empty stack is undefined behaviour: check empty() first.
  • Store positions rather than values when the answer needs an index or a distance.
  • Choose >= or > on purpose: it decides how equal values are treated.
Watch it run

Try your own input

Practise on LeetCode