Next Greater Element
In this page:
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;
}Login to try C/C++/Java code in the editor
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;
}Login to try C/C++/Java code in the editor
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;
}Login to try C/C++/Java code in the editor
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;
}Login to try C/C++/Java code in the editor
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;
}Login to try C/C++/Java code in the editor
🔒
Chapter Quiz — Complete all 5 topics to unlock
0/5 topics done
Complete these topics first: