Getting everything ready for you…

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

0s

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

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

  1. Scan from the right. Elements that are ≤ the current one can never be the "next greater" for anything further left — discard them.
  2. 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);
    }
}

Solve Next Greater Element online · All practice problems