Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Pretend the array is written twice in a row; then wrapping is just walking further right.
  2. 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