072. Next Smaller Element

Why this mechanism works

Reverse the comparison from next-greater search, not the traversal direction. Pending values are nondecreasing from bottom to top. An incoming smaller value resolves a suffix of larger pending candidates, which explains why the data structure remains a stack.

State and boundaries

stack stores unresolved indices in nondecreasing value order. answer remains -1 until a first smaller successor arrives.

Protocol

1. Scan left to right.
2. While the top value exceeds the incoming value, pop and answer it.
3. Push the new index.
4. Leave unresolved answers at -1.

Visualization

values: 4 2 5 1
2 resolves 4
1 resolves 5 and 2
answers: 2 1 1 -1

Python implementation

def next_smaller(nums):
    answer = [-1] * len(nums)
    stack = []
    for i, value in enumerate(nums):
        while stack and nums[stack[-1]] > value:
            answer[stack.pop()] = value
        stack.append(i)
    return answer

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 next_smaller: answer = [-1] * len(nums)
nums=[4, 2, 5, 1]; answer=[-1, -1, -1, -1]

L3 next_smaller: stack = []
nums=[4, 2, 5, 1]; answer=[-1, -1, -1, -1]; stack=[]

L4 next_smaller: for i, value in enumerate(nums):
nums=[4, 2, 5, 1]; answer=[-1, -1, -1, -1]; stack=[]; i=0; value=4

L7 next_smaller: stack.append(i)
nums=[4, 2, 5, 1]; answer=[-1, -1, -1, -1]; stack=[0]; i=0; value=4

L4 next_smaller: for i, value in enumerate(nums):
nums=[4, 2, 5, 1]; answer=[-1, -1, -1, -1]; stack=[0]; i=1; value=2

L6 next_smaller: answer[stack.pop()] = value
nums=[4, 2, 5, 1]; answer=[2, -1, -1, -1]; stack=[]; i=1; value=2

L7 next_smaller: stack.append(i)
nums=[4, 2, 5, 1]; answer=[2, -1, -1, -1]; stack=[1]; i=1; value=2

L4 next_smaller: for i, value in enumerate(nums):
nums=[4, 2, 5, 1]; answer=[2, -1, -1, -1]; stack=[1]; i=2; value=5

... 1 intermediate state changes omitted ...

L4 next_smaller: for i, value in enumerate(nums):
nums=[4, 2, 5, 1]; answer=[2, -1, -1, -1]; stack=[1, 2]; i=3; value=1

L6 next_smaller: answer[stack.pop()] = value
nums=[4, 2, 5, 1]; answer=[2, -1, 1, -1]; stack=[1]; i=3; value=1

L6 next_smaller: answer[stack.pop()] = value
nums=[4, 2, 5, 1]; answer=[2, 1, 1, -1]; stack=[]; i=3; value=1

L7 next_smaller: stack.append(i)
nums=[4, 2, 5, 1]; answer=[2, 1, 1, -1]; stack=[3]; i=3; value=1

L2 next_smaller: answer = [-1] * len(nums)
nums=[1, 1]; answer=[-1, -1]

L3 next_smaller: stack = []
nums=[1, 1]; answer=[-1, -1]; stack=[]

L4 next_smaller: for i, value in enumerate(nums):
nums=[1, 1]; answer=[-1, -1]; stack=[]; i=0; value=1

L7 next_smaller: stack.append(i)
nums=[1, 1]; answer=[-1, -1]; stack=[0]; i=0; value=1

L4 next_smaller: for i, value in enumerate(nums):
nums=[1, 1]; answer=[-1, -1]; stack=[0]; i=1; value=1

L7 next_smaller: stack.append(i)
nums=[1, 1]; answer=[-1, -1]; stack=[0, 1]; i=1; value=1

Why the solution is correct

An unresolved index has encountered no smaller successor yet. The first incoming value that is smaller will reach and remove it after resolving any larger tops above it. The resulting answer is therefore the earliest qualifying successor.

Time and space

O(n) time and O(n) space by one push and at most one pop per index.

Common mistakes

Changing only the output sign rather than the comparison does not change the ordering invariant. Equal values must remain unresolved relative to one another.

Reasoning card

Transfer exercise

Return the previous strictly smaller index using a left-to-right stack that discards dominated history before answering the current position.