Practice › Stack & Queue
Next Greater Element II
Medium · Stack & Queue · Asked at Amazon, Google, Microsoft, Flipkart
The array is circular (after the last element comes the first). For each element, print the first greater element you meet when walking forward (wrapping around), or -1 if none exists.
Input
First line: n. Second line: n space-separated integers.
Output
n space-separated answers.
Constraints
- 1 ≤ n ≤ 10^5
- -10^9 ≤ a[i] ≤ 10^9
Run the monotonic-stack algorithm over indices 0 … 2n−1, using i % n.
Example 1
Input
3 1 2 1
Output
2 -1 2
Example 2
Input
5 1 2 3 4 3
Output
2 3 4 -1 4
Hints
- Pretend the array is written twice in a row; then wrapping is just walking further right.
- Run the usual next-greater monotonic stack over indices 0 … 2n − 1, using a[i % n], and only push indices from the first pass.
Approach
Keep a stack of indices whose next greater element is unknown, with decreasing values. Iterate i from 0 to 2n − 1, value a[i % n]: pop every index whose value is smaller and assign this value as its answer. Push i only when i < n. After two passes, every element has seen all others in circular order; whatever remains has no greater element (−1).
Complexity: O(n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n), ans(n, -1);
for (auto &x : a) cin >> x;
vector<int> st;
for (int i = 0; i < 2 * n; i++) {
long long v = a[i % n];
while (!st.empty() && a[st.back()] < v) {
ans[st.back()] = v;
st.pop_back();
}
if (i < n) st.push_back(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:]
ans, st = [-1] * n, []
for i in range(2 * n):
v = a[i % n]
while st and a[st[-1]] < v:
ans[st.pop()] = v
if i < n:
st.append(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();
ans[i] = -1;
}
int[] st = new int[n];
int top = 0;
for (int i = 0; i < 2 * n; i++) {
long v = a[i % n];
while (top > 0 && a[st[top - 1]] < v) ans[st[--top]] = v;
if (i < n) st[top++] = i;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append(ans[i]).append(i + 1 < n ? " " : "");
System.out.println(sb);
}
}Solve Next Greater Element II online · All practice problems