Find the next Greater element

The problem, simply

You get an array of numbers. For each number, find the first number to its right that is bigger. If there is none, write -1.

Give back an array of answers, one per position.

A story to remember it

Picture it

Examples

Way 1: the simple way

For each position, look to the right one by one until you find a bigger number.

1. For each i, start j at i + 1.
2. Move j right until arr[j] > arr[i], and write arr[j].
3. If j runs off the end, write -1.

class Solution {
    public int[] nextGreater(int[] arr) {
        int n = arr.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = -1;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] > arr[i]) {      // first bigger one wins
                    ans[i] = arr[j];
                    break;
                }
            }
        }
        return ans;
    }
}

How long it takes: for a falling array like [5, 4, 3, 2], every i scans to the end, so about n * n / 2 checks, O(n^2). Extra room: O(1) besides the answer.

Way 2: the clever way

Walk from right to left and keep a pile of "kids who could still block someone", a stack. The pile is always in order: bigger at the bottom, smaller on top.

1. Start at the last index with an empty stack.
2. For arr[i], pop every value on top that is less than or equal to arr[i]. They are hidden behind arr[i] and can never be anyone's answer again.
3. Now the top, if any, is the first bigger number to the right. Write it, or -1 if the stack is empty.
4. Push arr[i], since it may block someone further left.

Each number is pushed once and popped at most once, so the whole walk is fast.

class Solution {
    public int[] nextGreater(int[] arr) {
        int n = arr.length;
        int[] ans = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();   // possible blockers
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= arr[i]) {
                stack.pop();                         // hidden behind arr[i]
            }
            ans[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(arr[i]);
        }
        return ans;
    }
}

How long it takes: each number goes onto the stack once and comes off at most once, so the total work is O(n), even though there is a loop inside a loop. Extra room: the stack can hold all n numbers when the array is falling, O(n).

Watch out for

• Some versions want the index of the next greater element, not its value. Push indices onto the stack and compare arr[stack.peek()].
• The left to right version also works: keep indices of numbers still waiting for an answer, and when a bigger number comes, pop them and fill their answers. Both are O(n).
• The nested while makes people say O(n^2). Explain the "pushed once, popped once" argument out loud.

What interviewers ask next

• Circular array, where the search wraps around to the start. Walk i from 2n - 1 down to 0 and use arr[i % n]. The first pass fills the stack with what lies "after the end".
• Next smaller element. Same code, flip the comparison: pop values greater than or equal to arr[i].
• Daily temperatures: how many days until a warmer day? Store indices, and the answer is j - i.
• Next greater element for a list of query numbers (LeetCode 496). Run this once on the big array, save answers in a hash map, then look each query up.
• Stock span and largest rectangle in a histogram use the same stack that keeps its values in order.

Remember this

Grown-up words: the group of possible blockers is a monotonic stack (its values only go one way, here decreasing from bottom to top), the first taller kid is the next greater element, and "pushed once, popped once" is amortized analysis.