Workspace

Problem workspace

3 day streakD

Next Smaller Element

MediumStacksMonotonic stacks

The challenge

For each position, return the first strictly smaller value to its right, or -1.

Integer values may repeat or be negative. Results are values, not indices.

Example

[4,8,5,2,25] → [2,5,2,-1,-1].

Use the walkthrough below to inspect the input and each state change.

See Next Smaller Element, step by step

Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.

Zero-based input · top labeled explicitlyLIFO
Input and stack stateCurrent input index: -1. Main stack bottom to top: []. Auxiliary stack · bottom → top: []. Read the input in order. The stack keeps only the state needed to resolve the next item.40815223254Main stack · bottom → top ↑emptyAuxiliary · bottom → top ↑empty
Current input index
—
Main stack size
0
Step 01 / 10

Start with an empty stack

Read the input in order. The stack keeps only the state needed to resolve the next item.

Answer so far

Not recorded yet
Main stack · bottom → top
Empty
Auxiliary stack · bottom → top
Empty
View exact input and state

Input: [4,8,5,2,25]

Main stack: []. Auxiliary stack · bottom → top: [].

Put it into code

Keep unresolved indices with non-decreasing values.

Indices are zero-based. C++ uses C++17 or later.

def solve(values):
    n = len(values)
    answer, stack = [-1] * n, []
    for step in range(n):
        i = step % n
        while stack and values[stack[-1]] > values[i]:
            j = stack.pop()
            answer[j] = values[i]
        if step < n: stack.append(i)
    return answer

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap