Next Greater Element

Overview

Next greater element (NGE) for each element is the first element to its right that is strictly greater. If none, return -1 (or a sentinel). A monotonic stack of indices (values decreasing bottom to top) gives O(n): scan left to right; when arr[i] > arr[top], arr[i] is the NGE for the popped index.

When to Use

• Next greater to the right — classic; stack of indices, pop when current value is greater.
• Circular array — run indices 0..2n-1 with value at i % n.
• Next greater in a subarray — same pattern with bounds.

How It Works

Stack holds indices j that have not yet found their NGE. For each i: while stack non-empty and arr[stack[top]] < arr[i], pop j and set result[j] = arr[i]; then push i. Stack stays decreasing by value.

Example 1: Standard Next Greater (Return Value)

function nextGreaterElement(arr: number[]): number[] {
  const n = arr.length;
  const result = new Array(n).fill(-1);
  const stack: number[] = [];
  for (let i = 0; i < n; i++) {
    while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
      result[stack.pop()!] = arr[i];
    }
    stack.push(i);
  }
  return result;
}

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

Example 2: Return Index Instead of Value

Store the index of the next greater element (or -1). When you pop j, set result[j] = i instead of arr[i].

function nextGreaterIndex(arr: number[]): number[] {
  const n = arr.length;
  const result = new Array(n).fill(-1);
  const stack: number[] = [];
  for (let i = 0; i < n; i++) {
    while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
      result[stack.pop()!] = i;
    }
    stack.push(i);
  }
  return result;
}

Example 3: Next Greater Element II (Circular)

Each element may look past the end and wrap to the start. Iterate i from 0 to 2*n - 1, use value at idx = i % n. When you pop j, set result[j] = arr[idx]. Only push indices 0..n-1 (e.g. push when i < n) so each index is in the stack at most once.

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

Example 4: NGE with Duplicate Values

The same logic works when the array has duplicates. Strictly "first greater to the right" is still well-defined; we use strict inequality (arr[j] < arr[i]) so when values are equal we do not pop (the one to the right is not "greater").

Example 5: Previous Greater Element (To the Left)

For each i, find the nearest index j < i such that arr[j] > arr[i]. Scan left to right; before pushing i, pop indices whose value is ≤ arr[i]. The top of the stack (if any) after popping is the index of the previous greater element for i. Result[i] = arr[stack[top]] or -1.

function previousGreaterElement(arr: number[]): number[] {
  const n = arr.length;
  const result = new Array(n).fill(-1);
  const stack: number[] = [];
  for (let i = 0; i < n; i++) {
    while (stack.length > 0 && arr[stack[stack.length - 1]] <= arr[i]) stack.pop();
    if (stack.length > 0) result[i] = arr[stack[stack.length - 1]];
    stack.push(i);
  }
  return result;
}

Summary

• NGE: monotonic stack (decreasing); pop when current value is greater; assign value (or index) on pop.
• Circular: iterate 2n with i % n; push only first n indices. See Monotonic Stack, Daily Temperatures.