Next Greater Element II

Problem

Given a circular integer array nums, return an array answer such that answer[i] is the next greater element of nums[i] — the first value strictly greater than nums[i] that you encounter walking forward, wrapping around the end if needed.

If no such value exists, answer[i] = -1.

Intuition

The non-circular version (#496) solves this with a monotonic stack: walk the array, pop everything smaller than the current value, record the current value as their answer.

The circular twist is that after the last index we keep looking at the first index, the second, and so on — until we either find something larger or have done a full extra lap.

The trick: simulate the circular walk by iterating 2 * n times and indexing with i % n. The first n iterations seed the stack with unresolved indices; the second n iterations get one more shot at resolving them — but we don't push anything new during the second lap, since pushing past n cannot change any answer.

Approach

impl Solution {
    pub fn next_greater_elements(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut answer = vec![-1; n];

        for i in 0..n {
            for k in 1..n {
                let j = (i + k) % n;
                if nums[j] > nums[i] {
                    answer[i] = nums[j];
                    break;
                }
            }
        }

        answer
    }
}

function nextGreaterElements(nums: number[]): number[] {
  const n = nums.length;
  const answer = new Array<number>(n).fill(-1);

  for (let i = 0; i < n; i++) {
    for (let k= 1; k < n; k++) {
      const j= (i + k) % n;
      if (nums[j] > nums[i]) {
        answer[i] = nums[j];
        break;
      }
    }
  }

  return answer;
}

impl Solution {
    pub fn next_greater_elements(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut answer = vec![-1; n];
        let mut stack: Vec<usize> = Vec::with_capacity(n);

        for i in 0..(2 * n) {
            let x = nums[i % n];
            while let Some(&top) = stack.last() {
                if nums[top] < x {
                    stack.pop();
                    answer[top]= x;
                } else {
                    break;
                }
            }
            if i < n {
                stack.push(i);
            }
        }

        answer
    }
}

function nextGreaterElements(nums: number[]): number[] {
  const n = nums.length;
  const answer = new Array<number>(n).fill(-1);
  const stack: number[] = [];

  for (let i = 0; i < 2 * n; i++) {
    const x= nums[i % n];
    while (stack.length > 0 && nums[stack[stack.length - 1]] < x) {
      answer[stack.pop()!]= x;
    }
    if (i < n) {
      stack.push(i);
    }
  }

  return answer;
}

Trace

The 2n pass on nums = [1, 2, 1]:

Index 1 (value 2) never pops — it's the global max — so answer[1] stays -1. Final answer [2, -1, 2].

Edge cases

• All-equal array — nothing pops; every answer stays -1. Strict comparison is what protects this case.
• Strictly ascending [1, 2, 3, 4] — each element pops the previous on the first lap; the trailing 4 never pops; answer is [2, 3, 4, -1].
• Strictly descending [5, 4, 3, 2, 1] — first lap pushes all; second lap pops every index except the first (the global max) by visiting 5 again. Answer: [-1, 5, 5, 5, 5].
• Single element — the only -1 answer.

Takeaway

Circular variants of stack/queue problems usually become linear once you double the iteration range and suppress writes on the second lap. The data structure does not need to know the array is circular — only the index supplier does.

This is the same shape as a ring buffer scan in production systems: walk twice, mutate once.