Find the Next Greater Element - Codes with Visualization

Sasank Nasika
Written by
Sasank Nasika
Sasank Nasika
Sasank Nasika

Sasank is a Technical Content Writer with a strong background in competitive programming. He has solved nearly 1500 problems on LeetCode and achieved top rankings in LeetCode Weekly Contests, including global ranks of 171, 196, 206, 308, 352, and more. His expertise in algorithms and problem-solving is also reflected in his active participation on platforms like Codeforces. Sasank enjoys sharing his technical knowledge and helping others learn by creating clear and accessible content.

All articles by
Sasank Nasika
Edited by
Kaustubh Saini
Kaustubh Saini
Kaustubh Saini

Kaustubh Saini writes about software development in a way that’s easy to follow and genuinely helpful. He breaks down complex topics-from AI to the latest in tech-so they actually make sense. His goal is simple: help others learn, stay curious, and keep up with a fast-changing world.

All articles by
Kaustubh Saini
Last updated on
May 14, 2025
In this blog, we'll explore the "Next Greater Element" problem and discuss how to solve it efficiently using a stack-based algorithm to identify the next greater element for each item in a given array.
Find the Next Greater Element - Codes with Visualization

Problem Statement

Given an array, find the next greater element for each element in the array. The next greater element is the first element to the right that is larger than the current element. If no such element exists, consider it as -1.

For example, if the input array is [4, 5, 2, 10, 8], the output should be:

For 4, the next greater element is 5

For 5, the next greater element is 10

For 2, the next greater element is 10

For 10, there is no greater element, so -1

For 8, there is no greater element, so -1

Therefore, the output array would be [5, 10, 10, -1, -1].

Brute Force Approach

Explanation

The brute force approach is straightforward. For each element in the array, we scan through all the elements to its right until we find the first element that is greater than the current element.

The steps are:

  1. Initialize a result array of the same size as the input array
  2. For each element in the input array:
  • Look at all elements to its right
  • Find the first element that is greater than the current element
  • If such an element exists, add it to the result array; otherwise, add -1

The time complexity of this approach is O(n²) where n is the size of the array, because for each element, we might need to scan through the rest of the array in the worst case. The space complexity is O(n) for storing the result array.

Python Code

def next_greater_element_brute(arr):
    n = len(arr)
    result = [-1] * n  # Initialize result array with -1

    for i in range(n):
        # For each element, look at all elements to its right
        for j in range(i + 1, n):
            if arr[j] > arr[i]:
                # Found the next greater element
                result[i] = arr[j]
                break

    return result

C++ Code

#include <iostream>
#include <vector>

std::vector<int> nextGreaterElementBrute(std::vector<int>& arr) {
    int n = arr.size();
    std::vector<int> result(n, -1);  // Initialize result array with -1

    for (int i = 0; i < n; i++) {
        // For each element, look at all elements to its right
        for (int j = i + 1; j < n; j++) {
            if (arr[j] > arr[i]) {
                // Found the next greater element
                result[i] = arr[j];
                break;
            }
        }
    }

    return result;
}

Java Code

import java.util.Arrays;

public class NextGreaterElement {
    public static int[] nextGreaterElementBrute(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);  // Initialize result array with -1

        for (int i = 0; i < n; i++) {
            // For each element, look at all elements to its right
            for (int j = i + 1; j < n; j++) {
                if (arr[j] > arr[i]) {
                    // Found the next greater element
                    result[i] = arr[j];
                    break;
                }
            }
        }

        return result;
    }
}

Optimized Approach

Explanation

We can solve this problem more efficiently using a stack. This method allows us to process elements in a single pass through the array.

The key insight: elements that haven't yet found their next greater element need to be kept track of, and we can use a stack for this.

The steps are:

  1. Initialize a result array with -1's
  2. Initialize an empty stack
  3. Iterate through the array from right to left:
  • While the stack is not empty and the current element is greater than or equal to the element at the top of the stack, pop elements from the stack
  • If the stack is not empty after the while loop, the element at the top of the stack is the next greater element
  • Push the current element onto the stack

This approach has a time complexity of O(n) since each element is pushed and popped at most once. The space complexity is O(n) for the stack and the result array.

Let's Consider array = [4,5,2,10,8].

Initial State:

  • result = [-1, -1, -1, -1, -1]
  • stack = []

i = 4 → arr[4] = 8

  • Stack is empty ⇒ no greater element
  • Push 8

    result = [-1, -1, -1, -1, -1], stack = [8]

 i = 3 → arr[3] = 10

  • Pop 8 (since 8 <= 10)
  • Stack is now empty ⇒ no greater element
  • Push 10

    result = [-1, -1, -1, -1, -1], stack = [10]

 i = 2 → arr[2] = 2

  • Stack top 10 > 2 ⇒ next greater is 10
  • Set result[2] = 10
  • Push 2

    result = [-1, -1, 10, -1, -1], stack = [10, 2]

i = 1 → arr[1] = 5

  • Pop 2 (since 2 <= 5)
  • Stack top 10 > 5 ⇒ next greater is 10
  • Set result[1] = 10
  • Push 5

    result = [-1, 10, 10, -1, -1], stack = [10, 5]

 i = 0 → arr[0] = 4

  • Stack top 5 > 4 ⇒ next greater is 5
  • Set result[0] = 5
  • Push 4

    result = [5, 10, 10, -1, -1], stack = [10, 5, 4]

<visualization-box>

Python Code

def next_greater_element(arr):
    n = len(arr)
    result = [-1] * n  # Initialize result array with -1
    stack = []  # Stack to keep track of elements

    # Process all elements from right to left
    for i in range(n-1, -1, -1):
        # Remove elements from stack that are smaller than or equal to current
        while stack and stack[-1] <= arr[i]:
            stack.pop()

        # If stack is not empty, top element is the next greater element
        if stack:
            result[i] = stack[-1]

        # Push current element to stack
        stack.append(arr[i])

    return result

C++ Code

#include <vector>
#include <stack>

std::vector<int> nextGreaterElement(std::vector<int>& arr) {
    int n = arr.size();
    std::vector<int> result(n, -1);  // Initialize result array with -1
    std::stack<int> stack;  // Stack to keep track of elements

    // Process all elements from right to left
    for (int i = n - 1; i >= 0; i--) {
        // Remove elements from stack that are smaller than or equal to current
        while (!stack.empty() && stack.top() <= arr[i]) {
            stack.pop();
        }

        // If stack is not empty, top element is the next greater element
        if (!stack.empty()) {
            result[i] = stack.top();
        }

        // Push current element to stack
        stack.push(arr[i]);
    }

    return result;
}

Java Code

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

public static int[] nextGreaterElement(int[] arr) {
    int n = arr.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);  // Initialize result array with -1
    Stack<Integer> stack = new Stack<>();  // Stack to keep track of elements

    // Process all elements from right to left
    for (int i = n - 1; i >= 0; i--) {
        // Remove elements from stack that are smaller than or equal to current
        while (!stack.isEmpty() && stack.peek() <= arr[i]) {
            stack.pop();
        }

        // If stack is not empty, top element is the next greater element
        if (!stack.isEmpty()) {
            result[i] = stack.peek();
        }

        // Push current element to stack
        stack.push(arr[i]);
    }

    return result;
}


Conclusion

We've explored two methods to solve the "Next Greater Element" problem:
1. The brute force approach with O(n²) time complexity, which is simple but inefficient for large inputs.
2. The optimized stack-based approach with O(n) time complexity, which efficiently handles large inputs.
The stack-based solution shows how using the right data structure can transform an inefficient algorithm into an efficient one. This optimization pattern is common in array and sequence problems, where information about previous elements needs to be tracked.

FAQs

TAGS

Arrays
They’re judging your every word.
Our AI shows you how to sound confident and hireable — instantly.
Rehearse with a pro (AI)
Interview like it’s game day.
Simulate tough questions and sharpen your answers.
Simulate a real interview
FAQ Question
Arrow

FAQ Answer

Revolutionizing Interview Preparation with AI

Try it now - It’s free!