DSA-045 · One unresolved-index stack over a virtual doubled scan
Next Greater Element — Circular Array
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 9846 deterministic checks. Learner drafts are not executed.
Understand the problem
For each circular-array position, return the first strictly greater value encountered by moving forward around at most one full cycle.
- nums is non-null with 0–100,000 signed int values. Preserve it and return an int[] of the same length. Empty input returns an empty result without any modulo-by-zero operation.
- For each i, inspect circular distances 1..n-1 in increasing order. Return the value at the first position with value>nums[i], or -1 when none exists. Equal values do not count and a position cannot resolve itself.
- The numeric -1 is the declared absence sentinel, even though -1 may also be a legitimate next greater value for a smaller negative input. This value-only API does not distinguish those two cases; an index/optional API would be needed for that distinction. The n bound keeps 2*n safely within int.
Examples
Input:
[1,2,1]
Output:[2,-1,2]The last one wraps to the two at index one.
Input:
[-2,-1]
Output:[-1,-1]The first -1 is an actual greater value; the second is absence under the same value-only representation.
Before you start
- Stack top versus bottom and last-in-first-out order
- Loop invariants, checked arithmetic, and amortized analysis
Recognize the structure
This is a next-greater query with wraparound. Keep unresolved original positions and feed them values in encounter order; a virtual second pass exposes the head of the array to unresolved tail positions.
Try before revealing
Hint 1
What work can one larger incoming value finish for earlier positions?
Hint 2
How can the head of the array serve tail queries without copying the input?
Hint 3
Scan 2n virtual positions and push indices only in the first pass.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Search each circular successor sequence
For each i, try distances 1 through n-1 and stop at the first greater value. For [3,2,1], index zero finds none, index one wraps to three, and index two also wraps to three, yielding [-1,3,3]. This O(n²) baseline follows the circular-distance contract directly.
Improve the baseline
Store positions awaiting a greater value
Unresolved indices are pushed during the first pass. Their values are nonincreasing from stack bottom to top, because a larger incoming value resolves smaller tops first.
Use two virtual passes
At virtual step, read nums[step%n]. Pop and answer while the incoming value is strictly greater than the top’s value.
Push each original index only once
Insert index only while step<n. The second pass supplies candidates but creates no duplicate obligations. Any still-unresolved entry keeps the -1 sentinel.
Why it is correct
First encounter invariant
An unresolved position has seen no strictly greater value among its already-scanned forward successors. A newly arriving greater value is therefore its first such encounter and may finalize the answer.
Stack and circular coverage
If a lower stack entry could be resolved by an incoming value, any smaller or equal top above it is resolved first, so no eligible answer is hidden. Two passes expose every legal wrapped successor. An answer cannot first appear after a full cycle: that same greater value would already have been encountered within the previous cycle; equality prevents self-resolution.
Termination and absence
Each index is pushed once and popped at most once over 2n steps. A remaining entry has no greater value among its n-1 other circular positions, justifying -1. With n=0 the loop has no iterations and modulo is never evaluated.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.*;
public final class Solution {
public static int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] answer = new int[n]; Arrays.fill(answer, -1);
ArrayDeque<Integer> unresolved = new ArrayDeque<>();
for (int step = 0; step < 2 * n; step++) {
int index = step % n;
while (!unresolved.isEmpty() && nums[unresolved.peek()] < nums[index]) answer[unresolved.pop()] = nums[index];
if (step < n) unresolved.push(index);
}
return answer;
}
public static int[] baseline(int[] nums) {
int[] answer = new int[nums.length]; Arrays.fill(answer, -1);
for (int i = 0; i < nums.length; i++) for (int distance = 1; distance < nums.length; distance++) {
int index = (i + distance) % nums.length;
if (nums[index] > nums[i]) { answer[i] = nums[index]; break; }
}
return answer;
}
}
Read the meaningful blocks
Strict < pop condition
Equal values remain unresolved; changing the condition to ≤ would implement a different query and can allow self/equal resolution.
First-pass-only push
Second-pass duplication wastes state and breaks the one-obligation-per-original-index invariant.
Keep indices until resolution
The stack index identifies which output slot to fill, even when input values repeat.
Complexity
O(n) time by one push and at most one pop per original index, despite the nested while loop. O(n) stack workspace and O(n) returned output.
The successor-search baseline takes O(n²) time and O(n) returned storage, with O(1) other workspace. It is used only for bounded cases; large decreasing input checks wraparound through the optimized method.
Exact-state walkthroughs
Reveal normal and boundary traces
Wraparound resolves the tail
Input: [1,2,1] · Result: [2,-1,2]
Step 1 of 10: Initialize one output slot per original index.
A -1 slot is unresolved/absent until a first strictly greater encounter is recorded.
- 0: 1
- 1: 2
- 2: 1
Empty at this step.
- 0: -1
- 1: -1
- 2: -1
−1 follows the value-only contract and can mean absence or a legitimate greater value for a smaller negative input.
| Variable | Value |
|---|---|
| values | [1,2,1] |
| answer | [-1,-1,-1] |
| unresolvedIndices | [] |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 public static int[] nextGreaterElements(int[] nums) { 4 int n = nums.length; 5 int[] answer = new int[n]; Arrays.fill(answer, -1); 6 ArrayDeque<Integer> unresolved = new ArrayDeque<>(); 7 for (int step = 0; step < 2 * n; step++) { 8 int index = step % n; 9 while (!unresolved.isEmpty() && nums[unresolved.peek()] < nums[index]) answer[unresolved.pop()] = nums[index]; 10 if (step < n) unresolved.push(index); 11 } 12 return answer; 13 } 14 public static int[] baseline(int[] nums) { 15 int[] answer = new int[nums.length]; Arrays.fill(answer, -1); 16 for (int i = 0; i < nums.length; i++) for (int distance = 1; distance < nums.length; distance++) { 17 int index = (i + distance) % nums.length; 18 if (nums[index] > nums[i]) { answer[i] = nums[index]; break; } 19 } 20 return answer; 21 } 22 } 23
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize one output slot per original index.
A -1 slot is unresolved/absent until a first strictly greater encounter is recorded.
- values
[1,2,1]- answer
[-1,-1,-1]- unresolvedIndices
[]
- Push this original obligation once.
Unresolved values are nonincreasing bottom to top. The second pass supplies candidates, never duplicate source obligations.
- values
[1,2,1]- step
0- index
0- answer
[-1,-1,-1]- unresolvedIndices
[0]
- Resolve one original index at its first greater encounter.
Earlier scanned successors were not greater; this candidate is the first valid circular answer.
- values
[1,2,1]- step
1- index
1- resolvedIndex
0- answer
[2,-1,-1]- unresolvedIndices
[]
- Push this original obligation once.
Unresolved values are nonincreasing bottom to top. The second pass supplies candidates, never duplicate source obligations.
- values
[1,2,1]- step
1- index
1- answer
[2,-1,-1]- unresolvedIndices
[1]
- Push this original obligation once.
Unresolved values are nonincreasing bottom to top. The second pass supplies candidates, never duplicate source obligations.
- values
[1,2,1]- step
2- index
2- answer
[2,-1,-1]- unresolvedIndices
[1,2]
- Examine a wrapped candidate without pushing again.
Unresolved values are nonincreasing bottom to top. The second pass supplies candidates, never duplicate source obligations.
- values
[1,2,1]- step
3- index
0- answer
[2,-1,-1]- unresolvedIndices
[1,2]
- Resolve one original index at its first greater encounter.
Earlier scanned successors were not greater; this candidate is the first valid circular answer.
- values
[1,2,1]- step
4- index
1- resolvedIndex
2- answer
[2,-1,2]- unresolvedIndices
[1]
- Examine a wrapped candidate without pushing again.
Unresolved values are nonincreasing bottom to top. The second pass supplies candidates, never duplicate source obligations.
- values
[1,2,1]- step
4- index
1- answer
[2,-1,2]- unresolvedIndices
[1]
- Examine a wrapped candidate without pushing again.
Unresolved values are nonincreasing bottom to top. The second pass supplies candidates, never duplicate source obligations.
- values
[1,2,1]- step
5- index
2- answer
[2,-1,2]- unresolvedIndices
[1]
- Return the contract result.
The completed result follows the declared ordering, empty-state, and numeric semantics.
- result
[2,-1,2]
An equal plateau never resolves
Input: [2,2,2] · Result: [-1,-1,-1]
Step 1 of 8: Initialize one output slot per original index.
A -1 slot is unresolved/absent until a first strictly greater encounter is recorded.
- 0: 2
- 1: 2
- 2: 2
Empty at this step.
- 0: -1
- 1: -1
- 2: -1
−1 follows the value-only contract and can mean absence or a legitimate greater value for a smaller negative input.
| Variable | Value |
|---|---|
| values | [2,2,2] |
| answer | [-1,-1,-1] |
| unresolvedIndices | [] |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 public static int[] nextGreaterElements(int[] nums) { 4 int n = nums.length; 5 int[] answer = new int[n]; Arrays.fill(answer, -1); 6 ArrayDeque<Integer> unresolved = new ArrayDeque<>(); 7 for (int step = 0; step < 2 * n; step++) { 8 int index = step % n; 9 while (!unresolved.isEmpty() && nums[unresolved.peek()] < nums[index]) answer[unresolved.pop()] = nums[index]; 10 if (step < n) unresolved.push(index); 11 } 12 return answer; 13 } 14 public static int[] baseline(int[] nums) { 15 int[] answer = new int[nums.length]; Arrays.fill(answer, -1); 16 for (int i = 0; i < nums.length; i++) for (int distance = 1; distance < nums.length; distance++) { 17 int index = (i + distance) % nums.length; 18 if (nums[index] > nums[i]) { answer[i] = nums[index]; break; } 19 } 20 return answer; 21 } 22 } 23
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize one output slot per original index.
A -1 slot is unresolved/absent until a first strictly greater encounter is recorded.
- values
[2,2,2]- answer
[-1,-1,-1]- unresolvedIndices
[]
- Push this original obligation once.
Unresolved values are nonincreasing bottom to top. The second pass supplies candidates, never duplicate source obligations.
- values
[2,2,2]- step
0- index
0- answer
[-1,-1,-1]- unresolvedIndices
[0]
- Push this original obligation once.
Unresolved values are nonincreasing bottom to top. The second pass supplies candidates, never duplicate source obligations.
- values
[2,2,2]- step
1- index
1- answer
[-1,-1,-1]- unresolvedIndices
[0,1]
- Push this original obligation once.
Unresolved values are nonincreasing bottom to top. The second pass supplies candidates, never duplicate source obligations.
- values
[2,2,2]- step
2- index
2- answer
[-1,-1,-1]- unresolvedIndices
[0,1,2]
- Examine a wrapped candidate without pushing again.
Unresolved values are nonincreasing bottom to top. The second pass supplies candidates, never duplicate source obligations.
- values
[2,2,2]- step
3- index
0- answer
[-1,-1,-1]- unresolvedIndices
[0,1,2]
- Examine a wrapped candidate without pushing again.
Unresolved values are nonincreasing bottom to top. The second pass supplies candidates, never duplicate source obligations.
- values
[2,2,2]- step
4- index
1- answer
[-1,-1,-1]- unresolvedIndices
[0,1,2]
- Examine a wrapped candidate without pushing again.
Unresolved values are nonincreasing bottom to top. The second pass supplies candidates, never duplicate source obligations.
- values
[2,2,2]- step
5- index
2- answer
[-1,-1,-1]- unresolvedIndices
[0,1,2]
- Return the contract result.
The completed result follows the declared ordering, empty-state, and numeric semantics.
- result
[-1,-1,-1]
Test the contract
Input:
[]
Output:[]No modulo operation.
Input:
[5]
Output:[-1]No other position.
Input:
[2,2,2]
Output:[-1,-1,-1]Equality does not resolve.
Input:
[3,2,1]
Output:[-1,3,3]Wrapped greater candidates.
Common mistakes and counterexamples
Push again during the second pass
Counterexample: [1,2,1] should have exactly three original obligations.
Push only when step<n.
Resolve on equal values
Counterexample: [2,2] has no strictly greater value for either position.
Pop only smaller values.
Assume -1 always proves absence
Counterexample: [-2,-1] has a real next greater value -1 for the first position.
Honor the value-only contract or return indices to remove ambiguity.
Follow-ups
Return circular distances.
Store the virtual resolution step and compute step-originalIndex for the first greater encounter. Return an explicit absence value; prove distances stay in 1..n-1.
Remove circularity.
Scan once with the same unresolved-index mechanism. Remaining positions have no greater value to their right, so a second pass would introduce invalid wrapped answers.
Query greater-or-equal values.
Use a different equality policy and explicitly exclude the original position at distance zero/full n. Simply changing < to ≤ in the doubled scan can resolve a position with itself.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 147/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.