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
- 1 ≤ n ≤ 10^5
- -10^9 ≤ a[i] ≤ 10^9
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
- An element that is ≥ the current one can never be the answer for anything to the right of the current one.
- 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