Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediummonotonic-stack

Next Greater Element II

Problem (restated)

Circular array: for each index i, find the next strictly greater element to the right, wrapping around once. If none exists, -1.

Intuition

Same decreasing stack as linear next-greater, but walk the array twice (2n steps with i % n) so wrap-around candidates can resolve earlier indices.

Approaches

Circular next-greater (2n scan)

Tested only

Time O(n)Space O(n)

Idea. Indices stack, decreasing by value. On each step pop while current is greater and write ans[popped] = nums[i]. Only push during the first pass so each index is pending at most once.

Walkthrough. [1,2,1] → for index 2 (value 1), wrapping finds 2 → [2,-1,2].

Trade-offs. Still O(n): each index pushed once and popped at most once. Pushing on the second pass is unnecessary and can corrupt answers if not careful.

Solution

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

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

Template connection

Next-greater template + circular virtual length. Pair with NGE I (496) and Daily Temperatures (739).

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?