Code Logo

Next Greater Element

Published at23 Jul 2026
Created by
Medium 3 views
Like0

You are given an array of integers. For each element, find the next element to its right that is strictly greater than it. If no such element exists, the answer for that position should be -1.

This is a classic monotonic stack problem. The brute force approach uses nested loops to check every pair, running in O(n²). The stack approach solves it in O(n) by maintaining a decreasing stack of indices.

As you iterate through the array from left to right, you keep a stack of indices whose next greater element has not been found yet. When you encounter a new element, you compare it with the element at the top of the stack. If the current element is greater, then the current element is the next greater element for the index at the top of the stack. You record that and pop the stack, then continue checking the new top. Once the stack is empty or the top is greater than the current element, you push the current index onto the stack.

Example Input & Output

Example 1
Input
[13, 7, 6, 12]
Output
[-1, 12, 12, -1]
Explanation

13 is largest so no next greater. 7's next greater is 12. 6's next greater is 12. 12 has no next greater.

Example 2
Input
[4, 5, 2, 25]
Output
[5, 25, 25, -1]
Explanation

4's next greater is 5. 5's next greater is 25. 2's next greater is 25. 25 has no next greater.

Example 3
Input
[1, 2, 3, 4]
Output
[2, 3, 4, -1]
Explanation

Each element's next greater is the element immediately to its right except the last.

Algorithm Flow

Recommendation Algorithm Flow for Next Greater Element
Recommendation Algorithm Flow for Next Greater Element

Solution Approach

The key insight is maintaining a decreasing stack. The stack only ever contains indices whose values are in decreasing order. When a new value breaks that order (because it is larger), it resolves all the smaller values waiting in the stack.

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

The time complexity is O(n) because each element is pushed onto the stack once and popped at most once. The space complexity is O(n) for the result array and the stack.

Best Answers

java
import java.util.*;
class Solution {
    public int[] solution(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                result[stack.pop()] = nums[i];
            }
            stack.push(i);
        }
        return result;
    }
}