Next Greater Element II

medium array stack monotonic stack

Problem

Given a circular integer array nums, return the next greater number for every element. The next greater number of x is the first greater number encountered when traversing the array clockwise; return −1 if none exists.

Inputnums = [1, 2, 1]

Output[2, -1, 2]

The 1 at index 2 wraps around to index 0 and finds 2.

nums (comma-separated)

def next_greater_elements(nums):
    n = len(nums)
    ans = [-1] * n
    stack = []
    for i in range(2 * n):
        x = nums[i % n]
        while stack and nums[stack[-1]] < x:
            ans[stack.pop()] = x
        if i < n:
            stack.append(i)
    return ans

function nextGreaterElements(nums) {
  const n = nums.length;
  const ans = new Array(n).fill(-1);
  const stack = [];
  for (let i = 0; i < 2 * n; i++) {
    const x = nums[i % n];
    while (stack.length && nums[stack[stack.length - 1]] < x) {
      ans[stack.pop()] = x;
    }
    if (i < n) stack.push(i);
  }
  return ans;
}

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

vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    vector<int> ans(n, -1);
    vector<int> stack;
    for (int i = 0; i < 2 * n; i++) {
        int x = nums[i % n];
        while (!stack.empty() && nums[stack.back()] < x) {
            ans[stack.back()] = x; stack.pop_back();
        }
        if (i < n) stack.push_back(i);
    }
    return ans;
}

Explanation

This is the classic "next greater element" problem with a twist: the array is circular, so the search can wrap around from the end back to the beginning. The neat trick to handle the wrap is to pretend the array is doubled, looping 2 * n times while reading elements with nums[i % n].

We use a monotonic stack of indices for values still waiting for a greater number. When the current value x is greater than the value at the stack-top index, that index's answer is x, so we pop and set ans[popped] = x.

The important detail: we only push indices during the first n iterations (if i < n). The second lap exists purely to resolve elements that needed to wrap around — it never adds new waiting items.

Anything still on the stack after both laps has no greater element anywhere, so it keeps its default -1.

Example: nums = [1, 2, 1]. Index 0 (1) is resolved by 2 → answer 2. Index 1 (2) never finds anything larger → -1. Index 2 (1) wraps to index 0's 2 on the second lap → answer 2. Result: [2, -1, 2].

Time: O(n) Space: O(n)