☕ DSA Java Articles

Topics › Stacks and Queues › Monotonic Stack/Queue Problems [VVV. Imp]

Next Greater Element

Medium TUF ID 968 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given an array arr of n integers, find for every index i its next greater element: the first element to the right of i that is strictly greater than arr[i]. If no such element exists, the answer for i is -1. Return all answers as an array of length n.

Constraints: 1 ≤ n ≤ 10^5, and values fit in a 32-bit int.

The LeetCode version (496) wraps the same task differently: nums1 is a subset of nums2, all values are distinct, and for each value in nums1 you report the next greater element of that value’s position in nums2. Solve the array version once and the LeetCode version becomes a lookup; it is covered at the end.

Example 1

arr    = [4, 5, 2, 10, 8]
answer = [5, 10, 10, -1, -1]   // 2 sees 10 first; nothing to the right of 10 or 8 is bigger

Example 2

arr    = [6, 8, 0, 1, 3]
answer = [8, -1, 1, 3, -1]     // 8 is the maximum, so it has no next greater element

Example 3

arr    = [3, 3, 3]
answer = [-1, -1, -1]          // equal is not greater

Approach 1: Brute force

Intuition. Do exactly what the definition says. For each index, walk to the right and stop at the first element that is bigger. The scan for one index can take n steps when the answer is -1 or far away, which makes the whole thing quadratic.

Algorithm.

  1. For each i from 0 to n - 1, set res[i] = -1.
  2. For j from i + 1 to n - 1: if arr[j] > arr[i], set res[i] = arr[j] and stop the inner loop.
  3. Return res.
static int[] bruteForce(int[] arr) {
    int n = arr.length;
    int[] res = new int[n];
    for (int i = 0; i < n; i++) {
        res[i] = -1;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] > arr[i]) {
                res[i] = arr[j];
                break;
            }
        }
    }
    return res;
}

Complexity. Time O(n^2): a strictly decreasing array forces every inner scan to run to the end. Space O(1) besides the output.

For n = 10^5 that is about 5 × 10^9 comparisons. The waste is that each scan re-reads elements that earlier scans have already looked at.

Approach 2: Optimal, monotonic stack

Intuition. Process the array from right to left and keep only the elements to the right that could still be somebody’s answer. The key observation is about domination:

If arr[i] ≥ x for some x to the right of i, then x can never be the next greater element of anything at or left of i.

Suppose some j ≤ i had arr[j] < x. Then also arr[j] < x ≤ arr[i], and arr[i] is closer to j than x is, so the scan from j would stop at arr[i] (or earlier) and never reach x. So once we arrive at i, every candidate ≤ arr[i] can be thrown away for good.

After throwing those away, whatever is on top of the stack is the nearest element to the right that is bigger than arr[i], which is exactly the answer. Then arr[i] itself becomes the newest candidate for the elements further left.

The surviving candidates always form a monotonic stack: from the top downwards, values strictly increase and positions move further right. That shape is what makes the top the correct answer.

Algorithm.

  1. Create an empty stack.
  2. For i from n - 1 down to 0:
    • Pop while the top is ≤ arr[i].
    • res[i] is the top if the stack is non-empty, otherwise -1.
    • Push arr[i].
  3. Return res.
static int[] optimal(int[] arr) {
    int n = arr.length;
    int[] res = new int[n];
    Deque<Integer> st = new ArrayDeque<>();      // values; top is the nearest, deeper ones are strictly larger
    for (int i = n - 1; i >= 0; i--) {
        while (!st.isEmpty() && st.peek() <= arr[i]) st.pop();   // hidden behind arr[i] for everyone further left
        res[i] = st.isEmpty() ? -1 : st.peek();
        st.push(arr[i]);
    }
    return res;
}

Dry run on [4, 5, 2, 10, 8] (stack shown top first):

i arr[i] popped res[i] stack after push
4 8 none -1 8
3 10 8 -1 10
2 2 none 10 2, 10
1 5 2 10 5, 10
0 4 none 5 4, 5, 10

Result [5, 10, 10, -1, -1].

Complexity. Time O(n). The inner while can pop many elements at one index, but each element is pushed exactly once and therefore popped at most once, so the total number of pops over the whole run is at most n. Space O(n) for the stack, which ends up holding every element when the array is increasing, such as [1, 2, 3, 4]: scanning from the right, nothing is ever popped.

The mirror-image formulation. You can also scan left to right and keep a stack of indices that have not found their answer yet. When arr[j] arrives, it is the answer for every waiting index with a smaller value, so pop them and record arr[j]. Both versions are O(n); the right-to-left one reads more naturally because each answer is decided at the moment its index is processed.

The LeetCode 496 variant

When the queries come as values (nums1) that all appear in nums2 with distinct values, compute the next greater element of every position of nums2 once, store value → answer in a hash map, and answer each query with one lookup. Distinct values make the map key unambiguous.

static int[] nextGreaterOfSubset(int[] nums1, int[] nums2) {
    int[] nge = optimal(nums2);
    Map<Integer, Integer> answerOf = new HashMap<>();
    for (int i = 0; i < nums2.length; i++) answerOf.put(nums2[i], nge[i]);
    int[] res = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) res[i] = answerOf.get(nums1[i]);
    return res;
}

Time O(n + m) and space O(n) for n = nums2.length and m = nums1.length, compared with O(n · m) if each query scanned nums2 on its own.

Edge cases and pitfalls