Skip to content
Hello Python
Pattern1 Practice2 Interview

Monotonic Stack

Maintain ordered unresolved candidates for next-greater, next-smaller, and span problems. Learn its decision rule, maintained state, Python cost model, and transfer from a focused drill to a full Interview Problem.

Recognize it when

Consider Monotonic Stack when the prompt's constraints and required operations match this shape: Maintain ordered unresolved candidates for next-greater, next-smaller, and span problems.

Pybit demonstrates the Monotonic Stack decision pattern in a professional coding interview workspace.
On this page · Keep Only Unresolved Candidates

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Monotonic Stack Code Labs

Keep Only Unresolved Candidates

A monotonic stack stores candidates whose next qualifying element has not appeared. Its value order lets one new item resolve a suffix of weaker candidates at once.

Pop When the Answer Arrives

For next greater, pop while the current value is strictly greater than the top. The current index is the first qualifying answer because every earlier processed value failed to pop that candidate.

Trace Monotonic Pops

Reference
def increasing_stack_trace(values):
    stack=[]
    trace=[]
    for index,value in enumerate(values):
        popped=[]
        while stack and values[stack[-1]] < value:
            popped.append(stack.pop())
        stack.append(index)
        trace.append([index,popped,stack.copy()])
    return trace
Practice

Implement increasing_stack_trace(values). Return [index, popped_indexes, stack_indexes] for each value while maintaining an increasing stack.

Public tests

  • Pop resolved candidates

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Store Index or Value Deliberately

Store indexes when the answer needs distance, position, or access to parallel data. Store values only when position is irrelevant. Decide strict versus non-strict comparison explicitly so duplicates have correct ownership.

Find Next Greater Distances

Reference
def next_greater_distance(values):
    result=[0]*len(values)
    stack=[]
    for index,value in enumerate(values):
        while stack and values[stack[-1]] < value:
            previous=stack.pop()
            result[previous]=index-previous
        stack.append(index)
    return result
Practice

Implement next_greater_distance(values). Return distance to the next strictly greater value for each index, or 0.

Public tests

  • Resolve each index once

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose a Monotonic Stack or Heap

Use a monotonic stack for nearest qualifying neighbors in scan order. Use a heap for global best candidates where resolution order follows priority rather than adjacency. Every index is pushed and popped at most once, giving O(n) time and O(n) space.

Explain It in an Interview

Say: “The stack is monotone and contains only unresolved indexes. This current value is the first one able to resolve each popped index.” Then explain why remaining stack entries legitimately receive the sentinel.

Python Version Note

Python 3.11+

The examples use the standard Python syntax and containers supported by the browser Judge; the Monotonic Stack invariant is independent of a minor Python release.

Verify in Python docs(opens in a new tab)

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Monotonic Stack decision loopO(n)O(n)Nearest earlier elements under an ordering constraint can discard candidates permanently as soon as a later value dominates them. Stack indices increase from bottom to top and their values are strictly increasing after invalid candidates are removed.

Space

O(n) for the focused Maintain a Monotonic Stack implementation.

Assumptions

  • After removing earlier indices whose values are not strictly smaller, the stack top is the nearest earlier index with a strictly smaller value. Appending that index, or -1 when the stack is empty, therefore gives the exact previous-smaller result.
  • The bound includes real Python operations; no repeated slicing, linear list membership, or hidden sorting is treated as free.

Invariants Worth Saying Aloud

  1. State the precise Monotonic Stack invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. Stack indexes remain unresolved and monotone by value.
  3. Each index is pushed once and popped at most once.
  4. Nearest earlier elements under an ordering constraint can discard candidates permanently as soon as a later value dominates them. Preserve this property after every transition.
  5. Stack indices increase from bottom to top and their values are strictly increasing after invalid candidates are removed. Preserve this property after every transition.

When To Use Or Avoid Monotonic Stack

Use It When

  • Use Monotonic Stack when the prompt exposes the ordering, monotonicity, recurrence, or constraint that makes this decision safe.
  • Use it when stack indexes remain unresolved and monotone by value.

Choose Another Tool When

  • Avoid Monotonic Stack when its decision rule cannot eliminate work or preserve the required state.
  • Avoid forcing the label onto a prompt whose simpler direct scan already meets the constraints.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Moving state without a proof

Applying the pattern without proving its ordering, monotonicity, or window invariant can silently miss valid candidates.

Prevent it: Write the decision rule beside the loop and verify it against Maintain a Monotonic Stack before optimizing.

Avoid

def previous_smaller_indices(values):
    pass

Use instead

def previous_smaller_indices(values):
    stack = []
    result = []
    for index, value in enumerate(values):
        while stack and values[stack[-1]] >= value:
            stack.pop()
        result.append(stack[-1] if stack else -1)
        stack.append(index)
    return result

Where you will hit this: Maintain a Monotonic Stack(opens in a new tab)

Breaking the maintained state

Keeps equal-valued candidates and reports them even though the predecessor must be strictly smaller.

Prevent it: Use the public tests and preserve this state: Stack indexes remain unresolved and monotone by value.

Avoid

def previous_smaller_indices(values):
    stack = []
    result = []
    for index, value in enumerate(values):
        while stack and values[stack[-1]] > value:
            stack.pop()
        result.append(stack[-1] if stack else -1)
        stack.append(index)
    return result

Use instead

def previous_smaller_indices(values):
    stack = []
    result = []
    for index, value in enumerate(values):
        while stack and values[stack[-1]] >= value:
            stack.pop()
        result.append(stack[-1] if stack else -1)
        stack.append(index)
    return result

Where you will hit this: Maintain a Monotonic Stack(opens in a new tab)

Hiding Python work in the hot path

Python slicing, copying, membership in lists, or repeated sorting inside the loop can invalidate the intended complexity.

Prevent it: Count every slice, copy, sort, membership check, and container update before claiming O(n).

Avoid

def previous_smaller_indices(values):
    stack = []
    result = []
    for index, value in enumerate(values):
        while stack and values[stack[-1]] > value:
            stack.pop()
        result.append(stack[-1] if stack else -1)
        stack.append(index)
    return result

Use instead

def previous_smaller_indices(values):
    stack = []
    result = []
    for index, value in enumerate(values):
        while stack and values[stack[-1]] >= value:
            stack.pop()
        result.append(stack[-1] if stack else -1)
        stack.append(index)
    return result

Where you will hit this: Car Fleet(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.