Next Greater Value in a Circular Sequence
Solve this Problemarr (after the last element, the array wraps back to the first), find, for every position, the next element going clockwise that is strictly greater than it — searching at most once all the way around, and returning -1 if none exists.
The circularity can be simulated without ever duplicating the array: walk virtual indices from 0 up to 2n-1, mapping each one back into range with i % n. A monotonic decreasing stack of real indices handles the rest exactly as it would for a non-circular array — except now every index effectively gets two laps to find its answer instead of one. The only twist is to stop pushing new indices once the second lap begins (i >= n), since by then every index has already had its one chance to enter the stack. Each real index is still pushed exactly once and popped at most once across the whole walk, so the total work stays O(n) despite covering 2n virtual steps.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ arr.length ≤ 12 - ◆
0 ≤ arr[i] ≤ 100 - ◆
The array is circular: after the last element, searching continues from the beginning, wrapping at most once
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Scan Forward With Wraparound for Each Position
BruteFor every position i, scan up to n-1 steps forward using modular arithmetic (j = (i + k) % arr.length) to wrap past the end back to the beginning, looking for the first strictly greater value. If the wraparound scan returns to i without finding one, the answer is -1. Correct, but each position can trigger a scan through almost the entire array — O(n) per position, O(n²) overall.
O(n²)O(n)1class Solution {
2 public int[] nextGreaterCircular(int[] arr) {
3 int n = arr.length;
4 int[] result = new int[n];
5 for (int i = 0; i < n; i++) {
6 result[i] = -1;
7 for (int k = 1; k < n; k++) {
8 int j = (i + k) % n;
9 if (arr[j] > arr[i]) {
10 result[i] = arr[j];
11 break;
12 }
13 }
14 }
15 return result;
16 }
17}Optimal — Monotonic Stack Over Two Virtual Passes
OptimalSimulate walking the array twice in a row (indices 0 to 2n-1, each mapped back into range with i % n) without ever actually duplicating it. Keep a monotonic decreasing stack of real indices. Whenever the current value beats what's on top of the stack, pop it and record the current value as its answer — the same mechanic as the non-circular version, just given a second lap to find an answer that wraps around. Only push an index during the first lap (i < n), since by the second lap every index has already had its one chance to be pushed. Each real index is pushed once and popped at most once, so total work stays O(n) despite the 2n-length walk.
O(n)O(n)1class Solution {
2 public int[] nextGreaterCircular(int[] arr) {
3 int n = arr.length;
4 int[] result = new int[n];
5 Arrays.fill(result, -1);
6 Deque<Integer> stack = new ArrayDeque<>();
7 for (int i = 0; i < 2 * n; i++) {
8 int x = arr[i % n];
9 while (!stack.isEmpty() && arr[stack.peek()] < x) {
10 result[stack.pop()] = x;
11 }
12 if (i < n) stack.push(i);
13 }
14 return result;
15 }
16}