Next Greater Element — Problem Statement & Solution Guide
Problem Description
Given an array of integers, determine the next greater element for each position. The next greater element of a value at index i is defined as the first value to the right of i that is strictly larger than nums[i]. If no such value exists, the result for that position is -1.
Formally, for each index i from 0 to n-1, find the smallest index j such that j > i and nums[j] > nums[i]. If such a j exists, the output at index i is nums[j]; otherwise, it is -1.
This problem requires an efficient approach to handle large input sizes, avoiding the O(n^2) complexity of a naive nested loop solution. A monotonic stack technique is typically employed to achieve linear time complexity.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Next Greater Element"
WHY DOES IT MATTER?
This pattern is essential for problems involving 'next greater,' 'previous smaller,' or 'range minimum/maximum' queries. It demonstrates how to trade space for time by maintaining state (the stack) to avoid redundant comparisons, a fundamental concept in algorithmic optimization.
OPTIMIZATION CHALLENGE
The key insight is that once an element is popped from the stack, it will never be the next greater element for any subsequent element to its left. This 'amortized' popping ensures each element is pushed and popped at most once, leading to linear time complexity.
REAL-WORLD CONNECTION
Analogous to a call center queue where agents (stack) wait for the next available slot (greater element). When a new call comes in, it resolves all waiting agents who can be served by this new slot, ensuring the most recent eligible agent is handled first.
In interviews, explicitly state that you are using a 'monotonic stack' to signal familiarity with the pattern. Clarify whether you are storing indices or values; storing indices is often safer for handling duplicates and retrieving original positions.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The Next Greater Element problem is a canonical example of using a monotonic stack to optimize search operations. The naive approach involves scanning to the right for each element, resulting in O(n^2) time complexity, which is prohibitive for large datasets. The core insight is that we can process the array from right to left (or left to right with deferred resolution) while maintaining a stack of indices or values that are 'candidates' for being the next greater element. By keeping the stack monotonic (specifically, decreasing in value when processing right-to-left), we ensure that the top of the stack is always the closest greater element to the current position.
Interview Questions on This Problem
Q1At a fintech platform, we need to identify the next trading day where the stock price exceeds the current day's price for risk assessment. How would you model this if the data arrives in a stream?
Model this as a streaming version of Next Greater Element. Use a monotonic stack to store pending prices. As each new price arrives, pop elements from the stack that are smaller than the current price, recording the current index as their 'next greater' day. Push the current price onto the stack. This maintains O(1) amortized time per element.
Q2In a distributed system, how can the Next Greater Element pattern be applied to optimize log aggregation where we need to find the next error level higher than the current one?
Treat log levels as integers. Use a monotonic stack to track the most recent log entries. When a new log entry arrives, it resolves all previous entries in the stack that have a lower severity. This allows for real-time alerting without scanning the entire log history, reducing latency in high-throughput systems.
Q3Why is a monotonic stack preferred over a binary search tree for this specific problem?
A monotonic stack exploits the linear nature of the problem and the 'next' constraint (closest to the right). A BST would find *any* greater element but not necessarily the *first* one to the right. The stack maintains the relative order and proximity, ensuring O(n) total complexity versus O(n log n) for BST, and with lower constant factors due to simple pointer operations.
Examples
Input
nums = [4, 2, 7, 1, 8, 3, 9]
Output
[7, 7, 8, 8, 9, 9, -1]
Explanation: 1. Index 0 (4): The first element to the right greater than 4 is 7 at index 2. Result: 7. 2. Index 1 (2): The first element to the right greater than 2 is 7 at index 2. Result: 7. 3. Index 2 (7): The first element to the right greater than 7 is 8 at index 4. Result: 8. 4. Index 3 (1): The first element to the right greater than 1 is 8 at index 4. Result: 8. 5. Index 4 (8): The first element to the right greater than 8 is 9 at index 6. Result: 9. 6. Index 5 (3): The first element to the right greater than 3 is 9 at index 6. Result: 9. 7. Index 6 (9): No elements to the right. Result: -1.
Input
nums = [10, 5, 3, 8, 2, 12, 1]
Output
[12, 8, 8, 12, 12, -1, -1]
Explanation: 1. Index 0 (10): Scanning right, 5 and 3 are smaller. 8 is smaller. 2 is smaller. 12 is greater. Result: 12. 2. Index 1 (5): Scanning right, 3 is smaller. 8 is greater. Result: 8. 3. Index 2 (3): Scanning right, 8 is greater. Result: 8. 4. Index 3 (8): Scanning right, 2 is smaller. 12 is greater. Result: 12. 5. Index 4 (2): Scanning right, 12 is greater. Result: 12. 6. Index 5 (12): Scanning right, 1 is smaller. No greater element. Result: -1. 7. Index 6 (1): No elements to the right. Result: -1.
Input
nums = [1, 2, 3, 4, 5]
Output
[2, 3, 4, 5, -1]
Explanation: 1. Index 0 (1): Next element 2 is greater. Result: 2. 2. Index 1 (2): Next element 3 is greater. Result: 3. 3. Index 2 (3): Next element 4 is greater. Result: 4. 4. Index 3 (4): Next element 5 is greater. Result: 5. 5. Index 4 (5): No elements to the right. Result: -1.
Input
nums = [5, 4, 3, 2, 1]
Output
[-1, -1, -1, -1, -1]
Explanation: 1. Index 0 (5): All elements to the right (4, 3, 2, 1) are smaller. Result: -1. 2. Index 1 (4): All elements to the right (3, 2, 1) are smaller. Result: -1. 3. Index 2 (3): All elements to the right (2, 1) are smaller. Result: -1. 4. Index 3 (2): Element to the right (1) is smaller. Result: -1. 5. Index 4 (1): No elements to the right. Result: -1.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- The answer must be computed in O(n) time complexity
- The answer must be computed in O(n) space complexity
Optimal Approach & Strategy
Use a monotonic stack to store indices of elements for which the next greater element has not yet been found. Iterate from right to left, popping elements from the stack that are smaller than the current element, and assign the top of the stack as the next greater element for the current index.
Brute Force Approach
For each element, scan the array to the right until a larger element is found or the end is reached. This results in O(n^2) time complexity due to nested loops.
Verified Code Solutions
function nextGreaterElement(nums) {
const n = nums.length;
const res = new Array(n).fill(-1);
const stack = []; // store indices
for(let i=n-1;i>=0;--i){
while(stack.length && nums[stack[stack.length-1]]<=nums[i]) stack.pop();
if(stack.length) res[i]=nums[stack[stack.length-1]];
stack.push(i);
}
return res;
}
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(input.length===0) process.exit(0);
const n = input[0];
const nums = input.slice(1,1+n);
const res = nextGreaterElement(nums);
console.log(res.join(' '));#include <bits/stdc++.h>
using namespace std;
vector<int> nextGreaterElement(const vector<int>& nums) {
int n = nums.size();
vector<int> res(n, -1);
stack<int> st; // store indices
for(int i=n-1;i>=0;--i){
while(!st.empty() && nums[st.top()]<=nums[i]) st.pop();
if(!st.empty()) res[i]=nums[st.top()];
st.push(i);
}
return res;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
int n; if(!(cin>>n)) return 0; vector<int> nums(n); for(int i=0;i<n;++i)cin>>nums[i];
vector<int> ans=nextGreaterElement(nums);
for(int i=0;i<n;++i){if(i) cout<<' '; cout<<ans[i];}
cout<<'\n'; return 0;}
import java.io.*;
import java.util.*;
public class Main {
public static int[] nextGreaterElement(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Arrays.fill(res, -1);
Deque<Integer> stack = new ArrayDeque<>(); // store indices
for(int i=n-1;i>=0;--i){
while(!stack.isEmpty() && nums[stack.peek()]<=nums[i]) stack.pop();
if(!stack.isEmpty()) res[i]=nums[stack.peek()];
stack.push(i);
}
return res;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if(line==null || line.isEmpty()) return;
int n = Integer.parseInt(line.trim());
int[] nums = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<n;i++) nums[i]=Integer.parseInt(st.nextToken());
int[] ans = nextGreaterElement(nums);
StringBuilder sb = new StringBuilder();
for(int i=0;i<n;i++){
if(i>0) sb.append(' ');
sb.append(ans[i]);
}
System.out.println(sb.toString());
}
}def next_greater_element(nums):
n = len(nums)
res = [-1]*n
stack = [] # indices
for i in range(n-1, -1, -1):
while stack and nums[stack[-1]] <= nums[i]:
stack.pop()
if stack:
res[i] = nums[stack[-1]]
stack.append(i)
return res
def main():
import sys
data = sys.stdin.read().strip().split()
if not data:
return
n = int(data[0])
nums = list(map(int, data[1:1+n]))
ans = next_greater_element(nums)
print(' '.join(map(str, ans)))
if __name__ == "__main__":
main()function nextGreaterElement(nums) {
const n = nums.length;
const res = new Array(n).fill(-1);
const stack = []; // store indices
for(let i=n-1;i>=0;--i){
while(stack.length && nums[stack[stack.length-1]]<=nums[i]) stack.pop();
if(stack.length) res[i]=nums[stack[stack.length-1]];
stack.push(i);
}
return res;
}
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(input.length===0) process.exit(0);
const n = input[0];
const nums = input.slice(1,1+n);
const res = nextGreaterElement(nums);
console.log(res.join(' '));Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.