A plant’s duty roster is circular: after the last slot comes the first, and for each shift ops needs the next slot whose headcount is strictly higher so they can borrow a spare. The intern nested a wrap: from each index, scan up to n-1 steps around the ring. A week of slots returned in milliseconds. A year of hourly slots was still wrapping when the roster job timed out.

Next Greater Element II asks for the next strictly larger value, wrapping around. A nested wrap scan uses that and still pays O(n²). The payload is the next greater value, not a wait; wrapping is the other half of the prompt.

This is an interview writeup, not a LIFO lecture. The stack post owns push, pop, and why last-in is the ADT. Here we only care about a decreasing stack of indexes so the answer is a value, not a restart. Same family as Daily Temperatures: there the return is later index minus earlier index and the array is not circular; here the arithmetic and the wrap changed. Do not re-solve the waits on this prompt.

The problem

Given a circular int[] nums, return an int[] answer the same length. answer[i] is the next strictly greater value after index i, wrapping around the end to the start. If no such value exists, answer[i] is -1.

nums = [1, 2, 1]        →  [2, -1, 2]
nums = [1, 2, 3, 4, 3]  →  [2, 3, 4, -1, 4]

The first 1 finds 2. The 2 has nothing larger in the ring, so -1. The last 1 wraps past the start and finds 2. In the second row, 4 has nothing larger; the last 3 wraps to 4.

Note: The return is values, not waits. Daily Temperatures stores j - i and stops at the end. This prompt stores nums[j] and wraps. Do not mix the two.

Nested wrap scan is the honest brute force

From each i, walk up to n-1 steps wrapping with (i + step) % n (never step = 0, so an index never compares to itself), store the first strictly larger value, and leave -1 if you miss. Correct. Quadratic.

int[] nextGreaterElementsNested(int[] nums) {
    int n = nums.length;
    int[] answer = new int[n];
    Arrays.fill(answer, -1);
    for (int i = 0; i < n; i++) {
        for (int step = 1; step < n; step++) {
            int j = (i + step) % n;
            if (nums[j] > nums[i]) {
                answer[i] = nums[j];
                break;
            }
        }
    }
    return answer;
}

At n = 20 this is a rounding error. At a year of hourly slots you paid a nested wrap for a question a stack answers because each later value is a candidate for many earlier indexes at once: is this value strictly greater than the one still waiting on top?

Decreasing stack of indexes, twice around

The stack holds indexes that still have no strictly greater successor. Values at those indexes are decreasing from bottom to top — a monotonic decreasing stack. Walk i from 0 to 2n - 1. The candidate is nums[i % n]. Initialize answer to -1.

  • While the stack is not empty and nums[i % n] is strictly greater than nums[indexes.peek()], pop j and set answer[j] = nums[i % n].
  • If i < n, push i. The second lap only resolves; it must not enqueue the same indexes again.

Indexes left on the stack at the end never found a strictly greater value. They already hold -1 if you filled before the walk; default 0 is a legal value, not a miss.

Walk the first sample. Stack contents are indexes; the values are only for the comparison. Do not push once i >= n.

nums = [1, 2, 1]   n=3   answer starts [-1, -1, -1]

i=0  i%n=0  1   []           push 0                 [0]
i=1  i%n=1  2   1<2  pop 0   answer[0]=2  push 1    [1]
i=2  i%n=2  1   2>1          push 2                 [1, 2]
i=3  i%n=0  1   1==1         (no push)              [1, 2]
i=4  i%n=1  2   1<2  pop 2   answer[2]=2
                2==2         (no push)              [1]
i=5  i%n=2  1   2>1          (no push)              [1]

leftover [1] stays -1
answer = [2, -1, 2]

Index 0 (1) resolved on the first lap. Index 2 (1) needed the wrap to the 2 at index 1 — a different index. Index 1 (2) never finds a strictly greater value. All-equal input is the same leftover story: nothing pops, every slot stays -1.

The Java is that walk. Use Deque and ArrayDeque, not java.util.Stack. The stack stores indexes, not values; the payload written into answer is the greater value.

int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] answer = new int[n];
    Arrays.fill(answer, -1);
    Deque<Integer> indexes = new ArrayDeque<>();
    for (int i = 0; i < 2 * n; i++) {
        int val = nums[i % n];
        while (!indexes.isEmpty() && val > nums[indexes.peek()]) {
            int j = indexes.pop();
            answer[j] = val;
        }
        if (i < n) {
            indexes.push(i);
        }
    }
    return answer;
}

Time is O(n) — the loop is 2n, but each index is pushed once and popped at most once. Space is O(n) for the stack (a decreasing first lap holds every index). Do not quote the nested O(n²) as the intended bill.

Do not push on the second lap. Pushing i % n again duplicates indexes already waiting, and a later pop can overwrite a correct answer. Equals do not pop — the next greater must be strictly larger, so 1 on top of 1 stays. Never treat an index as its own next greater. A value may wrap to a different index that holds a larger value. It may not wrap to itself.

What interviewers usually poke next

  • Waits, not values, and not circular. Daily Temperatures is the same decreasing index stack; the payload is i - j and there is no second lap. Say the arithmetic and the wrap changed. Do not rewrite this method into that one.
  • One lap, still values. Drop the 2n walk and the i < n guard. Same payload. The last index can no longer wrap to a greater near the start.
  • Same monotonic family. Car Fleet and Largest Rectangle in Histogram use the same index-stack idea. Do not solve them on this prompt.
  • Next smaller. Flip > to <. The 2n walk, the first-lap-only push, and the value payload stay the same shape.
  • Right to left. Push from the end so a greater is already on the stack when you look. Same O(n); easier to botch the wrap because the circular successor is the one already stored.

You are done with this problem when you can walk [1, 2, 1] out loud, pop index 0 on the first lap and index 2 on the wrap, refuse to push after i >= n, and say why leftover 2 stays -1.