Next Greater Element

Given an int[], return an int[] where position i holds the first element to the right of nums[i] that's larger than nums[i]. If there's no such element, use -1.

Example 1

Text

Input:  [4, 6, 3, 2, 8, 1]
Output: [6, 8, 8, 8, -1, -1]
Explanation:
  4 -> 6 is the first larger value to its right
  6 -> skip 3 and 2, then 8
  3 -> 8, 2 -> 8
  8 and 1 -> nothing larger to the right

Example 2

Text

Input:  [5, 4, 3]
Output: [-1, -1, -1]

Brute force: look right from each element

For each i, scan the positions after i for the first larger value.

Java

import java.util.Arrays;

public class Main {
    static int[] nextGreater(int[] nums) {
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            result[i] = -1;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] > nums[i]) {
                    result[i] = nums[j];
                    break;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(nextGreater(new int[]{4, 6, 3, 2, 8, 1})));
        System.out.println(Arrays.toString(nextGreater(new int[]{5, 4, 3})));
    }
}

Output

[6, 8, 8, 8, -1, -1]
[-1, -1, -1]

Time: O(n²), for example on a decreasing array, where every scan goes to the end. Space: O(1) besides the output.

Optimal: a monotonic stack

Scan left to right, and keep a stack of indices whose answer hasn't been found yet. Their values are decreasing from bottom to top: if a larger value had come after a smaller one, the smaller one would have gotten its answer and been popped.

When a new value x arrives:

While the value at the top of the stack is smaller than x, x is the answer for that index. Record it and pop.
Push the current index. It's now waiting for its own answer.

Indices still on the stack at the end have no larger value to their right, so they keep -1.

Walkthrough with [4, 6, 3, 2, 8, 1] (the stack shows values, but stores their indices):

i	x	popped (answer = x)	stack after
0	4		[4]
1	6	4 → 6	[6]
2	3		[6, 3]
3	2		[6, 3, 2]
4	8	2 → 8, 3 → 8, 6 → 8	[8]
5	1		[8, 1]

8 and 1 are left on the stack, so their answers stay -1.

Java

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Main {
    static int[] nextGreater(int[] nums) {
        int[] result = new int[nums.length];
        Arrays.fill(result, -1);
        Deque<Integer> waiting = new ArrayDeque<>(); // indices, values decreasing bottom to top

        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            while (!waiting.isEmpty() && nums[waiting.peek()] < x) {
                result[waiting.pop()] = x;
            }
            waiting.push(i);
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(nextGreater(new int[]{4, 6, 3, 2, 8, 1})));
        System.out.println(Arrays.toString(nextGreater(new int[]{5, 4, 3})));
        System.out.println(Arrays.toString(nextGreater(new int[]{2, 2, 3})));
    }
}

Output

[6, 8, 8, 8, -1, -1]
[-1, -1, -1]
[3, 3, -1]

Time: O(n). There's a while inside a for, but each index is pushed once and popped at most once, so the total number of inner iterations over the whole run is at most n. Space: O(n) for the stack.

The stack is an ArrayDeque<Integer>: push and pop work at its head, and peek reads the head without removing it. It holds indices, not values, because the answer has to be written at the waiting element's position. The condition nums[waiting.peek()] < x is strict, so equal values do not count as "greater" (see [2, 2, 3]).

Variant: circular array (LeetCode 503)

In LeetCode 503, the search wraps around from the end to the start. Loop over the indices twice (0 to 2n - 1) and use i % n. Only the first pass pushes indices.

Java

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Main {
    static int[] nextGreaterCircular(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Deque<Integer> waiting = new ArrayDeque<>();
        for (int i = 0; i < 2 * n; i++) {
            int x = nums[i % n];
            while (!waiting.isEmpty() && nums[waiting.peek()] < x) {
                result[waiting.pop()] = x;
            }
            if (i < n) {
                waiting.push(i);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(nextGreaterCircular(new int[]{1, 2, 1})));
    }
}

Output

[2, -1, 2]

Question	Change
next smaller element	pop while `nums[top] > x`
previous greater element	scan right to left
days until a warmer temperature (LeetCode 739)	store `i - top` instead of `x`
largest rectangle in a histogram (LeetCode 84)	monotonic increasing stack of bar indices

Brute force: look right from each element

Optimal: a monotonic stack

Variant: circular array (LeetCode 503)

Related variations