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
- 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
#include <algorithm>
#include <optional>
#include <utility>
#include <string>
#include <vector>
using namespace std;
vector<int> solve(const vector<int>& values) {
int n = static_cast<int>(values.size());
vector<int> answer(n, -1), stack;
for (int step = 0; step < n; ++step) {
int i = step % n;
while (!stack.empty() && values[stack.back()] > values[i]) {
int j = stack.back(); stack.pop_back();
answer[j] = values[i];
}
if (step < n) stack.push_back(i);
}
return answer;
}