Skip to content
CodeItRaw
Path

LIFO and FIFO: brackets, monotonic stacks and deque windows.

Key ideas

  • A stack (LIFO): last opened closes first. In Python, a list: append and pop.
  • A monotonic stack holds elements still waiting for an answer; newcomers resolve them.
  • For a queue (FIFO) and a double-ended queue, use collections.deque.

Pattern

stack = []
for i, v in enumerate(values):
    while stack and stack[-1][1] < v:
        j, _ = stack.pop()
        # v answers j
    stack.append((i, v))

Finish these first:HashingTwo Pointers & Sliding Window

Lessons

Each lesson explains one idea from zero and ends with a few tasks. Lessons open in order; the explanation can be read at any time.

  1. 01

    The stack: last in, first out

    0/2 tasks

  2. 02

    When order matters a counter is not enough

    0/3 tasks

  3. 03

    The monotonic stack

    0/2 tasks

  4. 04

    Indices on the stack, a queue for windows

    0/2 tasks

Boss

  • 05

    Largest Rectangle

    Function

    • The boss opens when every lesson of the topic is finished. Solve it too and the topic is complete, and the topics after it open.