Find Previous Smaller Element
EasyPractice library · +10 XPstackmonotonic stack
Given a sequence of N integers, for each element, find the value of the nearest element to its left that is strictly smaller than it. If no such element exists, report -1.
For an element at index i, you need to find the largest index j < i such that arr[j] < arr[i]. If such a j exists, output arr[j]. Otherwise, output -1.
Input
The first line contains a single integer N. The second line contains N space-separated integers representing the sequence.
Output
Print N space-separated integers. The i-th integer is the previous smaller element for the i-th integer in the input sequence, or -1 if none exists.
Constraints
1 <= N <= 1000 -10^9 <= arr[i] <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB13 hidden tests
Example 1
Input
5 4 5 2 10 8
Output
-1 4 -1 2 2
For 4: -1. For 5: 4. For 2: -1. For 10: 2. For 8: 2.
Example 2
Input
3 1 2 3
Output
-1 1 2
For 1: -1. For 2: 1. For 3: 2.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 4 5 2 10 8
Example 2 input
3 1 2 3