Next Greater Element

Tags

Next Greater Element

Category

Stacks

Difficulty

Medium

Problem Statement

Given an array of integers, for each element find the next element in the array that is greater than it. The array is circular, meaning after the last element we wrap around to the beginning. If no greater element exists, the result for that position is -1.

Intuition

A monotonic decreasing stack efficiently tracks elements that have not yet found their next greater element. As we iterate through the array, whenever we encounter an element larger than the top of the stack, that element is the "next greater" for the stack's top. By iterating through the array twice (to handle the circular nature), every element gets a chance to find its next greater element.

Approach

  1. Initialize a result array of the same length, filled with -1.
  2. Initialize an empty stack that will store indices.
  3. Iterate through the array twice (indices 0 to 2n - 1) to handle circularity: a. Use i % n to get the actual index. b. While the stack is not empty and the current element is greater than the element at the index on top of the stack:
    • Pop the stack and set result[popped index] = current element. c. Push the current index onto the stack (only during the first pass, i.e., when i < n).
  4. Return the result array.

Pseudocode

function nextGreaterElement(array):
    n = len(array)
    result = [-1] * n
    stack = []  // stores indices

    for i from 0 to 2 * n - 1:
        circularIdx = i % n
        while stack is not empty and array[circularIdx] > array[stack.top()]:
            idx = stack.pop()
            result[idx] = array[circularIdx]
        if i < n:
            stack.push(circularIdx)

    return result

Time & Space Complexity

  • Time: O(n) where n is the length of the array. Each element is pushed and popped from the stack at most once across the two passes.
  • Space: O(n) for the stack and the result array.

Key Insights

  • The monotonic stack pattern is the classic approach for "next greater/smaller" problems.
  • Iterating twice through the array elegantly handles the circular wrap-around.
  • Elements remaining in the stack after both passes have no next greater element (they stay as -1).
  • We only push indices during the first pass to avoid processing duplicates.

Edge Cases

  • Array with a single element: result is [-1] since there is no other element.
  • Strictly decreasing array: every element's next greater is the maximum element (due to circularity), except the maximum itself which is -1.
  • All elements are equal: every result is -1.
  • Array with two elements: each element either has the other as its next greater or -1.

Linked mentions