Next Greater Element — O(n²) Timed Out at 10k Updates/sec

Every time a stock trader asks 'when will this stock price exceed today's value again?' or a weather app calculates 'how many days until a warmer day?', they're solving a variant of the Next Greater Element problem. It's not an academic curiosity — it's a pattern that shows up constantly in time-series analysis, histogram calculations, and real-time data stream processing. If you've ever felt like brute-force nested loops were the only way to compare elements across an array, this article will change how you think about sequential data.

The core problem is this: given an array of numbers, for each element find the first element to its right that is strictly greater than it. The naive approach — check every element against every other element to its right — costs O(n²) time. With millions of data points, that's catastrophically slow. The stack-based solution does the same job in a single pass, O(n) time, by remembering only the elements that are still 'waiting' to find their greater neighbour.

By the end of this article you'll understand not just how the monotonic stack solution works, but exactly why the stack is the right data structure here, when to reach for this pattern in the wild, how to handle circular arrays (a classic interview twist), and which gotchas trip up even experienced developers. You'll walk away with fully runnable Java code, a clear mental model, and the confidence to answer any interview variant of this question.

The Next Greater Element Problem: Why Brute Force Fails at Scale

The next greater element (NGE) for each element in an array is the first larger value to its right. If none exists, the answer is -1. For [2, 7, 3, 5, 4, 6, 8], the NGEs are [7, 8, 5, 6, 6, 8, -1]. The naive O(n²) solution compares every pair — fine for n=100, but at n=10,000 it performs 50 million comparisons, easily exceeding a 1-second timeout under high-throughput systems.

The key property: NGE is monotonic. As you scan right-to-left, you maintain a decreasing stack of candidates. Each element enters once and leaves once, yielding O(n) time and O(n) space. This stack-based approach eliminates redundant comparisons — when you find a larger element, all smaller elements to its left become irrelevant for future lookups.

NGE is the foundation for stock span problems, histogram area calculations, and parsing nested structures. In real systems, it appears in order-matching engines and priority scheduling where you need the next higher-priority task. The O(n) solution is mandatory when processing thousands of updates per second — the brute force version will be the first thing to fail under load.

Next Greater Element — Plain English and Algorithm

For each element in an array, find the first element to its right that is strictly greater. If none exists, the answer is -1.

Naive approach: for each element, scan right until a greater one is found. O(n^2).

Optimal approach — monotonic decreasing stack: 1. Initialize empty stack (stores indices). 2. For i from 0 to n-1: a. While stack non-empty and arr[stack[-1]] < arr[i]: pop j. result[j] = arr[i]. b. Push i. 3. Any index remaining in stack: result[j] = -1.

Worked example on [2, 1, 2, 4, 3]: i=0(2): push 0. stack=[0]. i=1(1): arr[0]=2 >= 1. Push 1. stack=[0,1]. i=2(2): arr[1]=1 < 2. Pop 1. result[1]=2. arr[0]=2 >= 2. Push 2. stack=[0,2]. i=3(4): arr[2]=2 < 4. Pop 2. result[2]=4. arr[0]=2 < 4. Pop 0. result[0]=4. Push 3. stack=[3]. i=4(3): arr[3]=4 >= 3. Push 4. stack=[3,4]. End: result[3]=-1, result[4]=-1. Result: [4, 2, 4, -1, -1].

The Brute-Force Baseline — And Why It Breaks Down

Before reaching for the elegant solution, let's be honest about the naive one. For each element at index i, you scan every element to its right until you find one that's larger. The moment you find it, that's your answer. If you reach the end without finding one, the answer is -1.

This works perfectly for small arrays. Write it once and you'll understand the problem deeply — that's actually valuable. The problem is cost. For an array of size n, the worst case is a descending array like [5, 4, 3, 2, 1]. Every element scans all the way to the right and finds nothing. That's n + (n-1) + (n-2) + ... + 1 comparisons — O(n²) time.

At 10,000 elements that means up to 100 million comparisons. At 1 million elements (totally normal for financial data), you're looking at a trillion operations. The brute force doesn't just 'run slow' — it becomes completely unusable. This is the exact moment where understanding data structures stops being academic and starts being a professional skill.

public class NextGreaterElementBruteForce {

    /**
     * For each element, scan rightward to find the first element
     * that is strictly greater. Returns -1 if none exists.
     *
     * Time:  O(n^2) — nested loops over the array
     * Space: O(n)   — result array
     */
    public static int[] findNextGreaterBruteForce(int[] prices) {
        int totalElements = prices.length;
        int[] nextGreater = new int[totalElements];

        for (int currentIndex = 0; currentIndex < totalElements; currentIndex++) {
            // Assume no greater element exists to the right
            nextGreater[currentIndex] = -1;

            // Scan every element to the right of currentIndex
            for (int lookAheadIndex = currentIndex + 1; lookAheadIndex < totalElements; lookAheadIndex++) {
                if (prices[lookAheadIndex] > prices[currentIndex]) {
                    // Found the first greater element — record it and stop scanning
                    nextGreater[currentIndex] = prices[lookAheadIndex];
                    break;
                }
            }
        }
        return nextGreater;
    }

    public static void main(String[] args) {
        int[] stockPrices = {73, 74, 75, 71, 69, 72, 76, 73};

        int[] result = findNextGreaterBruteForce(stockPrices);

        System.out.println("Stock Price  →  Next Greater Price");
        System.out.println("-------------------------------------");
        for (int i = 0; i < stockPrices.length; i++) {
            String nextVal = result[i] == -1 ? "none" : String.valueOf(result[i]);
            System.out.printf("    %-6d   →      %s%n", stockPrices[i], nextVal);
        }
    }
}

The Monotonic Stack — One Pass, O(n) Time

Here's the insight that makes everything click: when you're scanning left to right and you encounter a new element, it might be the 'next greater' answer for several previous elements simultaneously. The brute force misses this — it answers one question at a time. The stack lets you answer many questions at once.

The stack stores elements that are 'waiting' — they've been seen, but haven't found their next greater neighbour yet. Crucially, the stack stays in decreasing order from bottom to top (that's what makes it a monotonic stack). When a new element arrives: 1. While the stack isn't empty AND the new element is greater than the top of the stack — pop the top, and record the new element as its answer. 2. Push the new element onto the stack.

After one full pass, anything left in the stack never found a greater element, so their answer is -1.

Why does this work? Every element is pushed once and popped at most once. That's O(n) operations total, regardless of array shape. The stack ensures you never re-check a pair you've already resolved — you're spending zero effort on dead comparisons.

import java.util.Arrays;
import java.util.Stack;

public class NextGreaterElementStack {

    /**
     * Uses a monotonic decreasing stack to find the next greater element
     * for every position in a single left-to-right pass.
     *
     * Time:  O(n) — each element is pushed and popped at most once
     * Space: O(n) — stack can hold at most n elements (e.g. descending input)
     */
    public static int[] findNextGreater(int[] temperatures) {
        int totalDays = temperatures.length;
        int[] nextWarmerTemp = new int[totalDays];

        // Fill with -1 as the default: "no warmer day found"
        Arrays.fill(nextWarmerTemp, -1);

        // Stack holds INDICES (not values) so we can update the result array
        Stack<Integer> waitingIndices = new Stack<>();

        for (int today = 0; today < totalDays; today++) {

            // While today's temperature beats the temperature at the top of the stack...
            while (!waitingIndices.isEmpty()
                    && temperatures[today] > temperatures[waitingIndices.peek()]) {

                // ...the day on top of the stack has found its answer: today's temperature
                int resolvedDay = waitingIndices.pop();
                nextWarmerTemp[resolvedDay] = temperatures[today];
            }

            // Today hasn't found ITS next greater yet — add it to the waiting list
            waitingIndices.push(today);
        }

        // Any index still in the stack had no greater element to its right — stays -1
        return nextWarmerTemp;
    }

    public static void main(String[] args) {
        // Real-world framing: daily temperatures, find the next warmer day's temperature
        int[] dailyTemperatures = {73, 74, 75, 71, 69, 72, 76, 73};

        int[] result = findNextGreater(dailyTemperatures);

        System.out.println("Day  │ Temp │ Next Greater Temp");
        System.out.println("─────┼──────┼──────────────────");
        for (int day = 0; day < dailyTemperatures.length; day++) {
            String answer = result[day] == -1 ? "none" : String.valueOf(result[day]);
            System.out.printf(" %-3d │  %-3d │  %s%n", day + 1, dailyTemperatures[day], answer);
        }
    }
}

The Circular Array Variant — The Interview Curveball

Once you've nailed the linear version, interviewers love throwing this at you: what if the array is circular? Meaning, after the last element, you wrap around to the first. For [5, 4, 3, 2, 1], the next greater element for 4 is 5 (which is at index 0, to the 'right' when wrapping around).

The trick is elegant: simulate two passes over the array by iterating from index 0 to 2n-1, using modulo to wrap the index. Critically, on the second pass you should NOT push new indices onto the stack — you're only resolving elements that are still waiting. A clean way to enforce this: only push during the first pass (i < n).

This technique — doubling the loop with modulo — is a classic pattern for any circular array problem, not just Next Greater Element. Internalise it and you'll use it again.

import java.util.Arrays;
import java.util.Stack;

public class NextGreaterElementCircular {

    /**
     * Finds the next greater element in a circular array.
     * Elements wrap around: after the last element, search continues from index 0.
     *
     * Technique: iterate 0 to 2n-1, use (index % n) to wrap around.
     *            Only push indices during the first pass (index < n).
     *
     * Time:  O(n) — each element is pushed/popped at most once across both passes
     * Space: O(n) — stack size
     */
    public static int[] findNextGreaterCircular(int[] circularPrices) {
        int size = circularPrices.length;
        int[] nextGreater = new int[size];
        Arrays.fill(nextGreater, -1);

        Stack<Integer> waitingIndices = new Stack<>();

        // We loop 2*size to simulate wrapping around the array
        for (int iteration = 0; iteration < 2 * size; iteration++) {

            // Wrap the iteration index back into a valid array index
            int wrappedIndex = iteration % size;

            // Resolve all waiting elements that the current element is greater than
            while (!waitingIndices.isEmpty()
                    && circularPrices[wrappedIndex] > circularPrices[waitingIndices.peek()]) {
                int resolvedIndex = waitingIndices.pop();
                nextGreater[resolvedIndex] = circularPrices[wrappedIndex];
            }

            // Only push during the first full pass — second pass is for resolution only
            if (iteration < size) {
                waitingIndices.push(wrappedIndex);
            }
        }

        return nextGreater;
    }

    public static void main(String[] args) {
        // In a circular market: after price[last], the search continues from price[0]
        int[] circularMarketPrices = {5, 4, 3, 2, 1};

        int[] result = findNextGreaterCircular(circularMarketPrices);

        System.out.println("Circular Array: [5, 4, 3, 2, 1]");
        System.out.println();
        System.out.println("Price  │  Next Greater (circular)");
        System.out.println("───────┼──────────────────────────");
        for (int i = 0; i < circularMarketPrices.length; i++) {
            String answer = result[i] == -1 ? "none" : String.valueOf(result[i]);
            System.out.printf("  %-4d │  %s%n", circularMarketPrices[i], answer);
        }
    }
}

Next Greater Element Index Variant — Returning Distances, Not Values

LeetCode 739 'Daily Temperatures' is one of the most frequently asked Next Greater Element variants in real interviews. Instead of returning the next greater value, it asks: how many days until a warmer temperature? This is a small twist — instead of storing the value at the resolved index, you store the distance between the two indices.

This variant tests whether you truly understand what you're storing in the stack (indices, not values!) and whether you can adapt the pattern quickly. The stack logic is identical — the only change is one line in the result update.

This is also a great example of real-world application: think of it as 'wait time until the next event exceeds a threshold'. Used in financial analytics for breakout detection, in IoT sensor networks for anomaly detection, and in game development for AI aggression triggers.

import java.util.Arrays;
import java.util.Stack;

public class DaysUntilWarmerTemperature {

    /**
     * For each day, returns how many days you have to wait until a warmer temperature.
     * If no warmer temperature ever comes, the answer for that day is 0.
     *
     * This is LeetCode 739 — one of the most common Next Greater Element interview variants.
     *
     * Time:  O(n)
     * Space: O(n)
     */
    public static int[] daysUntilWarmer(int[] dailyTemps) {
        int totalDays = dailyTemps.length;
        int[] waitDays = new int[totalDays]; // default 0 means "never gets warmer"

        Stack<Integer> waitingDayIndices = new Stack<>();

        for (int today = 0; today < totalDays; today++) {

            // Today's temp resolves all past days that were waiting for something warmer
            while (!waitingDayIndices.isEmpty()
                    && dailyTemps[today] > dailyTemps[waitingDayIndices.peek()]) {

                int coldDay = waitingDayIndices.pop();

                // KEY DIFFERENCE from the value variant:
                // Store the GAP between the two days, not the temperature itself
                waitDays[coldDay] = today - coldDay;
            }

            waitingDayIndices.push(today);
        }

        // Days still in the stack never found a warmer day — waitDays stays 0
        return waitDays;
    }

    public static void main(String[] args) {
        int[] weekTemperatures = {73, 74, 75, 71, 69, 72, 76, 73};

        int[] daysToWait = daysUntilWarmer(weekTemperatures);

        System.out.println("Day  │ Temp │ Days Until Warmer");
        System.out.println("─────┼──────┼───────────────────");
        for (int day = 0; day < weekTemperatures.length; day++) {
            String wait = daysToWait[day] == 0 ? "never" : daysToWait[day] + " day(s)";
            System.out.printf(" %-3d │  %-3d │  %s%n", day + 1, weekTemperatures[day], wait);
        }
    }
}

Space Complexity Isn't Academic — It's Your Memory Budget

Every monotonic-stack solution you see online brags about O(n) time. They conveniently skip the fact that you're allocating a stack that could hold the entire array in the worst case. On a real backend processing millions of records, that stack depth matters. A strictly decreasing input like [9,8,7,6,5] forces your stack to store everything before any greater element appears. That's O(n) space. Not a problem when n is 10,000. A problem when n is 10 million and your process runs inside a Docker container with 512 MB of RAM.

The interviewer wants to hear you say "I accept this O(n) space cost because it's the price of O(n) time." But when you're shipping production code, you need to know whether your data stream is roughly monotonic. If it is, reconsider the approach or pre-allocate your stack capacity to avoid resize thrashing. The monotonic stack optimises time at the cost of space. Never pretend that cost is zero.

// io.thecodeforge — dsa tutorial

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

public class SpaceComplexityExample {
    // Worst-case: strictly decreasing input
    public static int[] nextGreaterElement(int[] values) {
        int[] result = new int[values.length];
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int idx = 0; idx < values.length; idx++) {
            while (!stack.isEmpty() && values[stack.peek()] < values[idx]) {
                int poppedIndex = stack.pop();
                result[poppedIndex] = values[idx];
            }
            stack.push(idx);  // This stack depth == idx+1 in worst case
        }
        // Remaining indices get -1
        while (!stack.isEmpty()) {
            result[stack.pop()] = -1;
        }
        return result;
    }
}

Edge Cases That Blow Up Your 'Correct' Solution

You wrote a textbook monotonic stack. It passes LeetCode. Your PR gets approved. Then production encounters an array with one element, or a trillion duplicates, or values that overflow an int. Suddenly you're debugging at 2 AM. Let's cut that off.

Single-element arrays are trivial but your loop must not throw. Duplicates are the real trap: the standard algorithm uses strict less-than (<) which leaves duplicates sitting in the stack, meaning they never get a 'next greater' element that's equal. That's actually correct per the problem definition (strictly greater), but if your business logic expects equal values to count, you change to <=. Don't discover this in a post-mortem.

Integer overflow? The problem typically constrains values to 10^9, but when you're computing distances for the index variant (result[idx] = poppedIndex - stack.peek()), you can get negative values if you're not careful with modular arithmetic for circular arrays. Stack the indices, not the values, and always check your bounds. A single off-by-one in a circular traversal produces garbage output that looks right for half the cases.

// io.thecodeforge — dsa tutorial

public class EdgeCaseGuard {
    public static int[] nextGreaterElement(int[] values) {
        // Guard: null or empty
        if (values == null || values.length == 0) {
            return new int[0];
        }
        int[] result = new int[values.length];
        // Use ArrayDeque with known capacity
        Deque<Integer> stack = new ArrayDeque<>(values.length);
        
        for (int idx = 0; idx < values.length; idx++) {
            // Use < for strict greater; change to <= for non-strict
            while (!stack.isEmpty() && values[stack.peek()] < values[idx]) {
                result[stack.pop()] = values[idx];
            }
            stack.push(idx);
        }
        // Fill leftovers with -1 (or null signal)
        while (!stack.isEmpty()) {
            result[stack.pop()] = -1;
        }
        return result;
    }
}

Python Implementation — Readability Without Sacrificing Performance

The monotonic stack solution in Python mirrors the Java approach but leverages Python's expressive syntax for cleaner code. Using a list as a stack (with [-1] indexing) and enumerate for iteration makes the algorithm immediately readable. Memory overhead is lower than naive approaches because we store only indices, and Python's dynamic lists handle resizing efficiently. The stack maintains decreasing values; when a larger number appears, we pop indices and set results. For circular variants, we simulate the wrap by iterating twice (modulo index) with a simple if i < len(arr) guard. Python's defaultdict is not needed here—just a plain list of -1s. The while-loop condition while stack and arr[stack[-1]] < arr[i] is the core insight. Output is O(n) time, O(n) space. Practically, this pattern appears in stock span, daily temperatures, and histogram problems. Always test with decreasing input (like [5,4,3,2,1]) to confirm all remain -1, and ascending input [1,2,3,4,5] to verify immediate replacement. Python's clarity makes debugging these edge cases trivial.

# io.thecodeforge — dsa tutorial

def next_greater_element(arr):
    n = len(arr)
    result = [-1] * n
    stack = []
    for i, val in enumerate(arr):
        while stack and arr[stack[-1]] < val:
            result[stack.pop()] = val
        stack.append(i)
    return result

# Example
print(next_greater_element([4, 5, 2, 25]))  # Output: [5, 25, 25, -1]

Edge Cases That Blow Up Your 'Correct' Solution — Python Edition

Even with the monotonic stack, Python-specific edge cases can break your implementation silently. The most common pitfall is large input arrays causing recursion depth errors if you mistakenly use recursion (never do—use iteration). Another is integer overflow: Python handles big ints gracefully, but if you're calculating distances (index variant), ensure you return i - stack[-1] not stack[-1] - i. Memory blow is rare due to Python's garbage collection, but holding references to massive lists in closures can cause memory leaks. Always test with input size 10^6 using range(10**6, 0, -1)—your stack may grow to O(n) and cause MemoryError on constrained environments. The circular variant's double iteration (2n) works, but if you use arr[i % n] without early exit, you'll compute results correctly but slower. Finally, nested list comprehensions for brute force are a trap—they look elegant but run O(n^2). Use timeit to prove O(n) vs O(n²) on edge cases. The 'off-by-one' bug occurs when popping from an empty stack; guard with while stack and ....

# io.thecodeforge — dsa tutorial

def nge(arr):
    n = len(arr)
    res = [-1] * n
    stack = []
    for i in range(2 * n):
        idx = i % n
        while stack and arr[stack[-1]] < arr[idx]:
            if stack[-1] < n:
                res[stack.pop()] = arr[idx]
            else:
                stack.pop()
        if i < n:
            stack.append(i)
    return res

print(nge([1, 2, 3, 4, 5]))  # Output: [2, 3, 4, 5, -1]