The challenge
Find the next strictly greater value for every position when the array is circular.
At most n − 1 subsequent positions are eligible. Missing answers are -1.
Example
[1,2,1] → [2,-1,2].
Use the walkthrough below to inspect the input and each state change.
See Next Greater Element in a Circular Array, 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: [1,2,1]
Main stack: []. Auxiliary stack · bottom → top: [].
Put it into code
Push indices only on the first pass; use the second pass to resolve them.
Indices are zero-based. C++ uses C++17 or later.
def solve(values):
n = len(values)
answer, stack = [-1] * n, []
for step in range(2 * 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 < 2 * 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;
}