Find the Previous Greater Element in an Array

Title: Find the Previous Greater Element in an Array

In this guide, you’ll learn how to find the previous greater element for every position in an array of integers. This is a classic monotonic stack problem that shows up frequently in coding interviews, and it builds directly on the pattern used for next greater element problems.

We’ll walk through the brute force idea first, then build an efficient O(n) solution using a stack. By the end, you’ll be able to trace the algorithm by hand, spot the common mistakes beginners make, and answer the interview follow-up questions that test a deeper understanding of the technique.

Understanding the Problem

Given an array of integers numbers, the previous greater element of the element at index i is the nearest element to its left that is strictly greater than numbers[i]. If no such element exists, the answer for that index is -1.

For example, in the array [4, 5, 2, 10, 8], the previous greater element of 2 (at index 2) is 5, because 5 is the closest element to the left of 2 that is bigger than it. The previous greater element of 4 (at index 0) is -1, since there is nothing to its left.

A naive solution checks, for every index i, every element to its left until it finds a bigger one. That takes O(n^2) time in the worst case. We can do much better with a stack.

Approach to Solve the Problem

The efficient approach scans the array once from left to right while maintaining a stack that always holds a strictly decreasing sequence of candidate previous-greater values.

1. Create an empty result array of the same length as numbers, and an empty Stack<Integer>.
2. For each index i from 0 to numbers.length - 1, repeat the steps below.
3. While the stack is not empty and the value on top of the stack is less than or equal to numbers[i], pop the stack. A popped value can never be the previous greater element of any later number, since numbers[i] is a closer and at least as large candidate.
4. After the popping loop, if the stack is empty, set result[i] = -1. Otherwise set result[i] to the value now on top of the stack.
5. Push numbers[i] onto the stack, since it may become the previous greater element for some later index.
6. Return the result array once the loop finishes.

Java Program

import java.util.Stack;

public class PreviousGreaterElement {

    public static int[] findPreviousGreater(int[] numbers) {
        int n = numbers.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();

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

        return result;
    }

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

        for (int i = 0; i < numbers.length; i++) {
            System.out.println("Previous greater of " + numbers[i] + " is " + result[i]);
        }
    }
}

Explanation of the Program

The stack only ever holds values that are strictly decreasing from bottom to top. Every time a new number arrives that is greater than or equal to the top of the stack, that top value can be discarded, because the new, closer number is a better (or equal) candidate for every future index.

The while loop performs this cleanup before we read the answer for numbers[i]. Once the loop stops, whatever remains on top of the stack, if anything, is by construction the nearest element to the left that is still greater than numbers[i].

After recording result[i], we push numbers[i] itself, since it is a valid candidate previous-greater element for whatever comes next. Each element is pushed exactly once and popped at most once, which is what keeps the algorithm linear.

Step-by-Step Trace

Let’s trace the algorithm on the input [3, 7, 1, 2, 8, 5] and watch how the stack grows and shrinks on each iteration.

At the end of each iteration, the stack holds a strictly decreasing sequence of unprocessed candidates, with its top element equal to the previous greater element of whichever number arrives next.

Examples

Here are a few inputs that highlight different behaviors of the algorithm.

Example 1: Strictly Increasing Array

When every element is larger than everything before it, no element ever has a previous greater element.

int[] numbers = {1, 2, 3, 4, 5};
int[] result = findPreviousGreater(numbers);
// result = [-1, -1, -1, -1, -1]

Example 2: Strictly Decreasing Array

When every element is smaller than everything before it, the previous greater element is always the number immediately to its left.

int[] numbers = {9, 7, 5, 3, 1};
int[] result = findPreviousGreater(numbers);
// result = [-1, 9, 7, 5, 3]

Example 3: Array with Duplicate Values

Duplicates show why the stack pops on <= rather than <. An equal value is not strictly greater, so it cannot be returned as the answer, and it gets removed from the stack in favor of the newer occurrence.

int[] numbers = {5, 3, 5, 2, 5};
int[] result = findPreviousGreater(numbers);
// result = [-1, 5, -1, 5, -1]

Common Mistakes to Avoid

These are the mistakes learners most often make when implementing this pattern.

• Popping on < instead of <= – leaves duplicate values on the stack, so an element equal to numbers[i] gets incorrectly returned as its previous greater element. Pop while the top of the stack is less than or equal to numbers[i].
• Reading the result before the while loop finishes – returns a value that is about to be popped, which is no longer a valid candidate. Only read result[i] after the while loop has finished popping.
• Pushing before checking the stack – pushes numbers[i] onto the stack before popping, so the while loop immediately compares numbers[i] against itself and pops it right back off. Always pop first, record the result, then push.
• Confusing previous greater with next greater – scanning the array from right to left, as in the next greater element problem, answers a different question. Scan left to right for the previous greater element.
• Treating the stack as if it stores indices – breaks if the code later tries to use the stack’s contents as positions when it actually stores numbers[i] values. Keep straight whether your stack holds values or indices, and comment the choice.

Edge Cases to Test

Check these input shapes before considering the implementation done.

• Empty array
• Single-element array
• Strictly increasing array
• Strictly decreasing array
• All identical elements
• Negative numbers mixed with positive numbers
• Integer.MIN_VALUE or Integer.MAX_VALUE present
• Null array reference

Additional Considerations

The algorithm runs in O(n) time. Although the while loop looks nested inside the for loop, each element is pushed onto the stack exactly once and popped at most once across the entire run, so the total number of push and pop operations is bounded by 2n.

Space complexity is O(n) in the worst case, when the input is strictly increasing and nothing is ever popped, leaving every element sitting on the stack at once.

Integer.MIN_VALUE and Integer.MAX_VALUE are worth testing explicitly because the comparison stack.peek() <= numbers[i] still behaves correctly at the boundaries of the int range, but it is easy to introduce an overflow bug if you later modify the algorithm to compare differences instead of raw values.

Interview Follow-up Questions

Once you can explain the base solution, be ready for these variations.

• What if you need the next greater element instead? – the same stack technique works, but you scan the array from right to left instead of left to right.
• What if you need the previous greater element’s index rather than its value? – push indices onto the stack instead of values, and compare numbers[stack.peek()] against numbers[i].
• What if the array is circular, so the search can wrap around to the end? – iterate over the array twice, conceptually using indices 0 to 2n - 1 with i % n, but only start recording results during the second pass.
• What if the input arrives as a stream and you must answer queries online? – maintain the same decreasing stack incrementally as each new value arrives; the amortized cost per element stays O(1) since each value is still pushed once and popped at most once.
• What if you cannot use an auxiliary data structure like a stack, only O(1) extra space? – you lose the linear-time guarantee; the fallback is the O(n^2) brute force scan that checks each element against everything to its left.

Conclusion

The previous greater element problem is a great way to practice the monotonic stack pattern, which also powers solutions to next greater element, largest rectangle in a histogram, and daily temperatures style problems. Once the stack invariant clicks, you’ll recognize the same shape in many other array problems.

Try adapting findPreviousGreater to return indices instead of values, or to handle the circular array variation from the interview follow-up questions, to make sure the pattern has really sunk in. You can learn more about array algorithms in the Arrays category.