Next Greater Element
The Next Greater Element (NGE) problem: given an array, for each element find the next element to the right that is greater than it. If none exists, output -1.
A naive approach takes O(n²). Using a stack, we can solve it in O(n) time.
Algorithm:
1. Iterate from right to left (or left to right using stack).
2. Maintain a stack of elements for which we haven't found the next greater.
3. While stack is not empty and top <= current element, pop (those have found their next greater).
4. If stack is empty, next greater = -1; else, next greater = stack top.
5. Push current element onto stack.
Java implementation:
public static int[] nextGreaterElements(int[] arr) {
int n = arr.length;
int[] result = new int[n];
Stack stack = new Stack<>();
// Traverse from left to right
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
int idx = stack.pop();
result[idx] = arr[i];
}
stack.push(i);
}
// Remaining elements have no greater
while (!stack.isEmpty()) {
result[stack.pop()] = -1;
}
return result;
}
// Example usage
int[] arr = {4, 5, 2, 25};
// result: [5, 25, 25, -1]
Two Minute Drill
- Next Greater Element problem solved with stack in O(n).
- Traverse left to right, maintain stack of indices with pending greater.
- When current element > arr[stack top], set result for those indices.
- Remaining indices get -1.
- Classic stack application, often asked in interviews.
Need more clarification?
Drop us an email at career@quipoinfotech.com