Practice › Stack & Queue
Next Greater Element
Medium · Stack & Queue · Asked at Amazon, Microsoft, Flipkart, Paytm, Samsung
For each element, print the first element to its right that is strictly greater, or -1 if none exists.
Input
First line: n. Second line: n integers.
Output
n answers, space-separated.
Constraints
- 1 ≤ n ≤ 10^5
Monotonic stack, scanning from the right — O(n).
Example 1
Input
4 4 5 2 25
Output
5 25 25 -1
Example 2
Input
4 13 7 6 12
Output
-1 12 12 -1
Hints
- Scan from the right. Elements that are ≤ the current one can never be the "next greater" for anything further left — discard them.
- Keep a stack of candidates: pop while top ≤ a[i]; the remaining top (if any) is the answer; then push a[i].
Approach
Process i from n − 1 down to 0 with a stack that is decreasing from bottom to top. Pop every value ≤ a[i]: a[i] is closer and at least as big, so those values are no longer useful. Whatever remains on top is the first greater element to the right, or -1 if the stack is empty. Then push a[i]. Each element is pushed and popped once, giving O(n).
Complexity: O(n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n), ans(n);
for (auto &x : a) cin >> x;
vector<long long> st;
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && st.back() <= a[i]) st.pop_back();
ans[i] = st.empty() ? -1 : st.back();
st.push_back(a[i]);
}
for (int i = 0; i < n; i++) cout << ans[i] << (i + 1 < n ? " " : "\n");
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, a = data[0], data[1 : data[0] + 1]
ans, stack = [-1] * n, []
for i in range(n - 1, -1, -1):
while stack and stack[-1] <= a[i]:
stack.pop()
if stack:
ans[i] = stack[-1]
stack.append(a[i])
print(*ans)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n], ans = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
ArrayDeque<Long> st = new ArrayDeque<>();
for (int i = n - 1; i >= 0; i--) {
while (!st.isEmpty() && st.peek() <= a[i]) st.pop();
ans[i] = st.isEmpty() ? -1 : st.peek();
st.push(a[i]);
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append(i > 0 ? " " : "").append(ans[i]);
System.out.println(sb);
}
}