☕ DSA Java Articles

Topics › Stacks and Queues › Monotonic Stack/Queue Problems [VVV. Imp]

Next Greater Element - 2

Medium TUF ID 969 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a circular integer array nums: the element after nums[n - 1] is nums[0]. For every index i, return the next greater element of nums[i], which is the first value strictly greater than nums[i] met when walking forward from i, wrapping around the end if needed. If a full lap finds nothing greater, the answer is -1.

Constraints (LeetCode 503): 1 ≤ n ≤ 10^4, -10^9 ≤ nums[i] ≤ 10^9.

Example 1

nums   = [1, 2, 1]
answer = [2, -1, 2]          // the last 1 wraps around and meets 2

Example 2

nums   = [1, 2, 3, 4, 3]
answer = [2, 3, 4, -1, 4]    // the final 3 wraps past 1, 2, 3 and stops at 4

Example 3

nums   = [5, 4, 3, 2, 1]
answer = [-1, 5, 5, 5, 5]    // every smaller element wraps to the 5 at the front

Compared with the plain Next Greater Element, the only change is that “to the right” now continues from the start of the array. Only the maximum value (every copy of it) can end with -1.

Approach 1: Brute force

Intuition. From each index, take up to n - 1 steps forward, using % n to wrap the index around, and stop at the first bigger value. Taking n - 1 steps visits every other position exactly once; the n-th step would land back on i itself, which can never be greater than itself.

Algorithm.

  1. For each i, set res[i] = -1.
  2. For step from 1 to n - 1: let j = (i + step) % n. If nums[j] > nums[i], record nums[j] and stop.
  3. Return res.
static int[] bruteForce(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    for (int i = 0; i < n; i++) {
        res[i] = -1;
        for (int step = 1; step < n; step++) {
            int j = (i + step) % n;
            if (nums[j] > nums[i]) {
                res[i] = nums[j];
                break;
            }
        }
    }
    return res;
}

Complexity. Time O(n^2): when many elements have no greater element, or it is far away, every scan is long. Space O(1) besides the output.

With n = 10^4 this is about 10^8 steps, which may pass, but it does not scale and it repeats work: neighbouring indices scan nearly the same elements.

Approach 2: Optimal, monotonic stack over the array laid out twice

Intuition. Write the array twice in a row: nums + nums. For an index i in the first copy, the positions i + 1, ..., i + n - 1 of this doubled array are exactly the circular walk from i: the rest of the first copy, then the beginning of the second copy up to just before i again. So the circular problem on nums becomes the ordinary next-greater problem on the doubled array, restricted to answers for the first n positions.

We run the standard right-to-left monotonic stack on the doubled array. Two details make it cheap and correct:

  1. No copy is needed. Virtual index i of the doubled array holds nums[i % n].
  2. Only the real copy records answers. Indices 2n - 1 down to n are a warm-up pass that loads the stack with exactly the candidates an index in the first copy would see after wrapping. Indices n - 1 down to 0 then record answers.

Why can the stack never give an answer from “too far away”? For i < n, any greater element on the circle appears somewhere in positions i + 1 ... i + n - 1, and the stack always reports the nearest greater element. Position i + n is a copy of nums[i] itself, and positions beyond it are copies of values already seen closer, so they can never be nearer than a genuine answer.

The pop rule is the one from the linear problem. When cur arrives, any candidate ≤ cur is hidden behind cur for every index further left, so it is popped for good. The top that survives is the nearest greater value.

Algorithm.

  1. Create an empty stack.
  2. For i from 2n - 1 down to 0:
    • cur = nums[i % n].
    • Pop while the top is ≤ cur.
    • If i < n, set res[i] to the top, or -1 if the stack is empty.
    • Push cur.
  3. Return res.
static int[] optimal(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Deque<Integer> st = new ArrayDeque<>();      // values; deeper entries are strictly larger
    for (int i = 2 * n - 1; i >= 0; i--) {
        int cur = nums[i % n];
        while (!st.isEmpty() && st.peek() <= cur) st.pop();
        if (i < n) res[i] = st.isEmpty() ? -1 : st.peek();   // only the second (real) pass records answers
        st.push(cur);
    }
    return res;
}

Dry run on [1, 2, 1], so n = 3 (stack shown top first):

virtual i i % n cur popped recorded stack after push
5 2 1 none (warm-up) 1
4 1 2 1 (warm-up) 2
3 0 1 none (warm-up) 1, 2
2 2 1 1 res[2] = 2 1, 2
1 1 2 1, 2 res[1] = -1 2
0 0 1 none res[0] = 2 1, 2

Result [2, -1, 2]. Notice that res[2] = 2 comes from the warm-up pass: the 2 it found is the copy at virtual index 4, which is position 1 reached by wrapping.

Complexity. Time O(n): 2n pushes, and each pushed value is popped at most once, so at most 2n pops in total. Space O(n) for the stack and the output; no doubled array is allocated.

A note on the warm-up. You might worry that the warm-up pushes values that later block real answers incorrectly. They cannot: a value from the second copy stays on the stack only while nothing between it and the current index is at least as big, which is precisely the condition for it to be the nearest greater element after wrapping.

Edge cases and pitfalls