← Back to DSA Course | Chapter 5: Stacks | Lesson 4 of 5

Next Greater Element

Next greater element is like looking down a line of people and finding, for each person, the first taller person standing to their right.

In this page:

  1. NGE Idea
  2. Using a Stack
  3. NGE Examples
  4. Circular Array
  5. NGE Practice
Syntax
markup 
result = [-1] * len(arr)
stack = []    # indexes still waiting
for i in range(len(arr)):
    while stack and arr[stack[-1]] < arr[i]:
        result[stack.pop()] = arr[i]
    stack.append(i)

NGE Idea

For each element in an array, the 'next greater element' is the first value to its right that's larger than it, or none if no such value exists, and computing this for every element efficiently is a classic stack problem.

Example: NGE Idea

#include <iostream>
using namespace std;
int main() {
    int arr[] = {4, 5, 2, 10};
    cout << "for 4, next greater is 5. for 10, no next greater exists" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {4, 5, 2, 10};
        System.out.println("for 4, next greater is 5. for 10, no next greater exists");
    }
}
arr = [4, 5, 2, 10]
print("for 4, next greater is 5. for 10, no next greater exists")
#include <stdio.h>
int main() {
    int arr[] = {4, 5, 2, 10};
    printf("for 4, next greater is 5. for 10, no next greater exists\n");
    return 0;
}

Using a Stack

A stack holds indexes of elements that are still waiting to find their next greater element, so as you scan left to right, you keep candidates on the stack until something bigger than the top comes along.

Example: Using a Stack

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
    vector<int> arr = {4, 5, 2, 10};
    vector<int> result(arr.size(), -1);
    stack<int> s;
    for (int i = 0; i < arr.size(); i++) {
        while (!s.empty() && arr[s.top()] < arr[i]) { result[s.top()] = arr[i]; s.pop(); }
        s.push(i);
    }
    for (int r : result) cout << r << " ";
    return 0;
}
import java.util.Stack;
public class Main {
    public static void main(String[] args) {
        int[] arr = {4, 5, 2, 10};
        int[] result = new int[arr.length];
        java.util.Arrays.fill(result, -1);
        Stack<Integer> s = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!s.isEmpty() && arr[s.peek()] < arr[i]) result[s.pop()] = arr[i];
            s.push(i);
        }
        for (int r : result) System.out.print(r + " ");
    }
}
arr = [4, 5, 2, 10]
result = [-1] * len(arr)
stack = []
for i in range(len(arr)):
    while stack and arr[stack[-1]] < arr[i]:
        result[stack.pop()] = arr[i]
    stack.append(i)
print(result)
#include <stdio.h>
int main() {
    int arr[] = {4, 5, 2, 10};
    int n = 4;
    int result[4] = {-1, -1, -1, -1};
    int s[4], top = -1;
    for (int i = 0; i < n; i++) {
        while (top >= 0 && arr[s[top]] < arr[i]) { result[s[top]] = arr[i]; top--; }
        s[++top] = i;
    }
    for (int i = 0; i < n; i++) printf("%d ", result[i]);
    return 0;
}

NGE Examples

This runs in O(n) despite looking like it might need nested loops, because a monotonic stack ensures each element is pushed and popped at most once across the entire scan, not once per other element.

Example: NGE Examples

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
    vector<int> arr = {1, 3, 2, 4};
    vector<int> result(arr.size(), -1);
    stack<int> s;
    for (int i = 0; i < (int)arr.size(); i++) {
        while (!s.empty() && arr[s.top()] < arr[i]) { result[s.top()] = arr[i]; s.pop(); }
        s.push(i);
    }
    cout << "each index pushed/popped at most once, O(n) despite the nested loop shape" << endl;
    return 0;
}
import java.util.Stack;
public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 4};
        int[] result = new int[arr.length];
        Stack<Integer> s = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!s.isEmpty() && arr[s.peek()] < arr[i]) result[s.pop()] = arr[i];
            s.push(i);
        }
        System.out.println("each index pushed/popped at most once, O(n)");
    }
}
arr = [1, 3, 2, 4]
result = [-1] * len(arr)
stack = []
for i in range(len(arr)):
    while stack and arr[stack[-1]] < arr[i]:
        result[stack.pop()] = arr[i]
    stack.append(i)
print("each index pushed/popped at most once, O(n)")
#include <stdio.h>
int main() {
    int arr[] = {1, 3, 2, 4};
    int n = 4;
    int result[4] = {-1, -1, -1, -1};
    int s[4], top = -1;
    for (int i = 0; i < n; i++) {
        while (top >= 0 && arr[s[top]] < arr[i]) { result[s[top]] = arr[i]; top--; }
        s[++top] = i;
    }
    printf("each index pushed/popped at most once, O(n)\n");
    return 0;
}

Circular Array

For a circular array, where the search continues from the beginning, you can simulate the wraparound by conceptually scanning through the array twice using the index modulo its length.

Example: Circular Array

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
    vector<int> arr = {3, 8, 4};
    int n = arr.size();
    vector<int> result(n, -1);
    stack<int> s;
    for (int i = 0; i < 2 * n; i++) {
        int idx = i % n;
        while (!s.empty() && arr[s.top()] < arr[idx]) { result[s.top()] = arr[idx]; s.pop(); }
        if (i < n) s.push(idx);
    }
    for (int r : result) cout << r << " ";
    return 0;
}
import java.util.Stack;
public class Main {
    public static void main(String[] args) {
        int[] arr = {3, 8, 4};
        int n = arr.length;
        int[] result = new int[n];
        java.util.Arrays.fill(result, -1);
        Stack<Integer> s = new Stack<>();
        for (int i = 0; i < 2 * n; i++) {
            int idx = i % n;
            while (!s.isEmpty() && arr[s.peek()] < arr[idx]) result[s.pop()] = arr[idx];
            if (i < n) s.push(idx);
        }
        for (int r : result) System.out.print(r + " ");
    }
}
arr = [3, 8, 4]
n = len(arr)
result = [-1] * n
stack = []
for i in range(2 * n):
    idx = i % n
    while stack and arr[stack[-1]] < arr[idx]:
        result[stack.pop()] = arr[idx]
    if i < n:
        stack.append(idx)
print(result)
#include <stdio.h>
int main() {
    int arr[] = {3, 8, 4};
    int n = 3;
    int result[3] = {-1, -1, -1};
    int s[3], top = -1;
    for (int i = 0; i < 2 * n; i++) {
        int idx = i % n;
        while (top >= 0 && arr[s[top]] < arr[idx]) { result[s[top]] = arr[idx]; top--; }
        if (i < n) s[++top] = idx;
    }
    for (int i = 0; i < n; i++) printf("%d ", result[i]);
    return 0;
}

NGE Practice

The key insight to internalize is that whenever a new value is larger than the stack's top, that top element has just found its next greater element and gets popped off, repeating until the stack's top is bigger or the stack is empty.

Example: NGE Practice

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
    vector<int> arr = {2, 1, 2, 4, 3};
    vector<int> result(arr.size(), -1);
    stack<int> s;
    for (int i = 0; i < (int)arr.size(); i++) {
        while (!s.empty() && arr[s.top()] < arr[i]) {
            cout << "index " << s.top() << " (" << arr[s.top()] << ") found NGE " << arr[i] << endl;
            result[s.top()] = arr[i];
            s.pop();
        }
        s.push(i);
    }
    return 0;
}
import java.util.Stack;
public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 1, 2, 4, 3};
        int[] result = new int[arr.length];
        Stack<Integer> s = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!s.isEmpty() && arr[s.peek()] < arr[i]) {
                System.out.println("index " + s.peek() + " (" + arr[s.peek()] + ") found NGE " + arr[i]);
                result[s.pop()] = arr[i];
            }
            s.push(i);
        }
    }
}
arr = [2, 1, 2, 4, 3]
result = [-1] * len(arr)
stack = []
for i in range(len(arr)):
    while stack and arr[stack[-1]] < arr[i]:
        top = stack.pop()
        print("index", top, "(", arr[top], ") found NGE", arr[i])
        result[top] = arr[i]
    stack.append(i)
#include <stdio.h>
int main() {
    int arr[] = {2, 1, 2, 4, 3};
    int n = 5;
    int result[5] = {-1, -1, -1, -1, -1};
    int s[5], top = -1;
    for (int i = 0; i < n; i++) {
        while (top >= 0 && arr[s[top]] < arr[i]) {
            printf("index %d (%d) found NGE %d\n", s[top], arr[s[top]], arr[i]);
            result[s[top]] = arr[i];
            top--;
        }
        s[++top] = i;
    }
    return 0;
}
Related Topics

Balanced Parentheses · Monotonic Stack · Stack Implementation · Stack Introduction

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
Common Mistakes
  1. Using two nested loops, which is O(n^2), when a monotonic stack does it in O(n).
  2. Pushing values instead of indexes, so the answer array cannot be updated at the right position.
  3. Forgetting that elements left on the stack at the end have no greater element and should be set to -1.
🔒

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Balanced Parentheses Next Lesson → Monotonic Stack

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.