Getting everything ready for you…

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

0s

Practice › Stack & Queue

Previous Smaller Element

Easy · Stack & Queue · Asked at Amazon, Microsoft, Flipkart

For every element, print the nearest element to its left that is strictly smaller than it, or -1 if there is none.

Input

First line: n. Second line: n space-separated integers.

Output

n space-separated answers.

Constraints

Keep a stack of candidates. Pop everything ≥ the current value; the top that remains is the answer; then push the current value.

Example 1

Input

5
4 5 2 10 8

Output

-1 4 -1 2 2

Example 2

Input

3
3 3 3

Output

-1 -1 -1

Hints

  1. An element that is ≥ the current one can never be the answer for anything to the right of the current one.
  2. So keep a stack of increasing values: pop while top ≥ current; the remaining top is the answer.

Approach

Scan left to right with a stack. For a[i], pop every value ≥ a[i] — they are hidden behind a[i] for all future elements. If the stack is empty the answer is −1, otherwise it is the top. Then push a[i]. Each element is pushed and popped at most once.

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), st;
    for (auto &x : a) cin >> x;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && st.back() >= a[i]) st.pop_back();
        cout << (st.empty() ? -1 : st.back()) << (i + 1 < n ? " " : "\n");
        st.push_back(a[i]);
    }
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
a = data[1:]
st, res = [], []
for x in a:
    while st and st[-1] >= x:
        st.pop()
    res.append(st[-1] if st else -1)
    st.append(x)
print(*res)

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[] st = new long[n];
        int top = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            long x = sc.nextLong();
            while (top > 0 && st[top - 1] >= x) top--;
            sb.append(top == 0 ? -1 : st[top - 1]).append(i + 1 < n ? " " : "");
            st[top++] = x;
        }
        System.out.println(sb);
    }
}

Solve Previous Smaller Element online · All practice problems