Find the Next Greater Element in an Array

Title: Find the Next Greater Element in an Array

The next greater element problem is one of the most common stack-based interview questions, and it shows up again and again under different names. In this guide, we will explore how to find, for every element in an array, the first element to its right that is strictly larger than it. You will learn a clean O(n) approach using a stack, see a complete Java program, walk through a step-by-step trace, and practice the interview follow-ups that usually come after the base solution.

Understanding the Problem

Given an integer array nums, we want to produce a result array of the same length where result[i] holds the first element to the right of index i that is strictly greater than nums[i]. If no such element exists, result[i] should be -1.

For example, for the input {4, 5, 2, 10, 8}, the next greater element of 4 is 5, the next greater element of 5 is 10, and the next greater element of 10 does not exist because nothing to its right is larger, so it becomes -1.

A brute-force solution checks, for every index, every element to its right until it finds a larger one. That works but costs O(n squared) in the worst case, such as a strictly decreasing array. A stack lets us answer every index in a single linear pass.

Approach to Find the Next Greater Element

The key idea is to scan the array from right to left while keeping a stack of ‘candidate’ values, that is, values that could still be the next greater element for something further to the left. Here are the steps:

1. Create a result array of the same length as nums and an empty stack.
2. Iterate i from the last index down to 0.
3. While the stack is not empty and its top is less than or equal to nums[i], pop it; those values can never be the answer for nums[i] or for anything to the left of it.
4. After the popping stops, the stack is either empty, meaning no greater element survives, or its top is the next greater element for nums[i].
5. Set result[i] to -1 if the stack is empty, otherwise to the stack’s top value.
6. Push nums[i] onto the stack so it becomes a candidate answer for elements further to the left.
7. After the loop finishes, result holds the next greater element for every index.

Java Program to Find the Next Greater Element

Let us put the approach into a full, compilable Java program:

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

public class NextGreaterElement {

    public static int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= nums[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(nums[i]);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {4, 5, 2, 10, 8};
        int[] result = nextGreaterElements(nums);

        System.out.println("Array: " + Arrays.toString(nums));
        System.out.println("Next Greater Elements: " + Arrays.toString(result));
    }
}

Explanation of the Program

• The method nextGreaterElements takes the array nums and returns a new array of the same size.
• A Deque<Integer> is used as the stack because the standard Stack class is older and ArrayDeque is the recommended stack implementation in modern Java.
• The loop walks the array from the last index to the first so that, at the moment we process nums[i], the stack already contains the useful candidates from everything to the right of i.
• The inner while loop discards stack values that are not strictly greater than nums[i], since a smaller or equal value can never be the next greater element for nums[i].
• After the inner loop, whatever remains on top of the stack, if anything, is the first value to the right of i that is strictly greater than nums[i].
• nums[i] is pushed last so it is available as a candidate for the next index processed, which is i - 1.

Step-by-Step Trace

Let us trace the algorithm on the input {4, 6, 4, 3, 8}, scanning from index 4 down to index 0.

At the end of each iteration, the stack holds a decreasing sequence of values that are still candidates for elements further to the left, and result[i] already holds the correct next greater element for index i.

Examples

Let us look at a few concrete runs to see how the stack behaves on different shapes of input.

Example 1: A Typical Mixed Array

int[] nums1 = {4, 5, 2, 10, 8};
System.out.println(Arrays.toString(nextGreaterElements(nums1)));
// Output: [5, 10, 10, -1, -1]

Each value finds a larger value somewhere to its right except 10 and 8, which are the two largest values and have nothing greater after them.

Example 2: A Strictly Decreasing Prefix

int[] nums2 = {13, 7, 6, 12};
System.out.println(Arrays.toString(nextGreaterElements(nums2)));
// Output: [-1, 12, 12, -1]

13 is the largest value in the array, so it never finds a next greater element. The smaller values that follow it do find one, since 12 is larger than both 7 and 6.

Example 3: A Fully Decreasing Array

int[] nums3 = {9, 5, 3, 1};
System.out.println(Arrays.toString(nextGreaterElements(nums3)));
// Output: [-1, -1, -1, -1]

When the array is strictly decreasing, every element is the largest value from its position to the end, so every entry in result is -1.

Common Mistakes to Avoid

Here are the slip-ups learners tend to make when implementing the stack-based next greater element solution:

• Defaulting to 0 instead of -1 – Java’s int[] initializes every slot to 0, so an element with no greater value to its right silently reports 0, which looks like a real answer instead of ‘none found’. Explicitly assign -1 when the stack is empty.
• Popping only on strict less-than – for arrays with duplicate values like {4, 6, 4, 3, 8}, using < instead of <= leaves an equal value on the stack, which then gets returned as the ‘next greater’ element even though it is only equal. Pop while stack.peek() <= nums[i].
• Forgetting to push nums[i] after computing result[i] – the current element is a valid candidate answer for everything still to its left, so skipping the push makes earlier indices compute their result against a stale, smaller stack. Always push right after assigning the result.
• Mixing left-to-right and right-to-left logic – the right-to-left version looks up the answer before pushing, while a left-to-right version resolves answers for earlier indices when a bigger value finally arrives. Combining the two styles produces a result array filled with elements that came before the current index instead of after it.
• Storing indices but printing them as if they were values – if the stack holds indices instead of raw numbers, printing stack.peek() directly gives a position in the array, not the next greater number. Decide upfront whether the stack holds values or indices and stay consistent.

Edge Cases to Test

Before you declare the implementation done, run the algorithm against these boundary inputs:

• Empty array
• Single-element array
• Strictly decreasing array (every result is -1)
• Strictly increasing array (every result is the next element)
• All elements identical
• Maximum value at the last index
• Integer.MAX_VALUE present
• Null array reference

Additional Considerations

A few points worth remembering about this algorithm:

1. Time complexity: Although there is a nested while loop, every value is pushed onto the stack exactly once and popped at most once across the entire run, so the total work is O(n), not O(n squared).
2. Space complexity: The result array is O(n), and the stack can hold up to n elements in the worst case, such as a strictly decreasing input where nothing ever gets popped. Overall extra space is O(n).
3. Why Integer.MAX_VALUE matters: An element equal to Integer.MAX_VALUE can never have a next greater element, so it is a useful stress value for confirming your -1 handling is correct.
4. Direction of traversal: Scanning right to left lets you look up the answer immediately because the stack always holds valid candidates for the current index. A left-to-right scan is also O(n) but needs to resolve earlier indices retroactively, which is harder to reason about.

Interview Follow-up Questions

Once the base version is working, an interviewer will usually probe deeper with questions like these:

• What if the array is circular, so the next greater element can wrap around to the front? – iterate the index range twice, from 0 to 2n - 1, using i % n to let elements near the end see candidates near the start, without physically duplicating the array.
• What if you need the next smaller element instead of the next greater one? – keep the same stack-based scan but flip the comparison in the pop condition; the complexity stays O(n).
• What if you are given nums1 and nums2, where nums1 is a subset of nums2, and need the next greater element for each nums1 entry within nums2? – compute the next-greater map for all of nums2 once using this stack approach, then answer each nums1 query with an O(1) lookup, for O(n + m) overall.
• What if the array is a stream of unknown length and you cannot rewind? – buffer unresolved elements on the stack as before, but accept that any element still on the stack when the stream ends has no next greater element; resolve entries only as larger values arrive.
• What if the array has billions of elements and must stay within a fixed memory budget? – note that the stack can hold the entire array in the worst case, such as a strictly decreasing input, so an exact streaming solution still needs O(n) auxiliary space; only an approximate or windowed answer can run in bounded memory.

Conclusion

In this guide, we solved the next greater element problem in Java using a single stack and a right-to-left scan, bringing the running time down from O(n squared) to O(n). You now have a complete program, a worked trace, concrete examples, and a checklist of common mistakes and interview follow-ups to lean on.

Try adapting the code to a circular array, to the next smaller element variant, or to the two-array lookup version to see how the same stack idea solves a whole family of problems. Happy coding!

You can learn more about Array techniques: Arrays