Next Smaller Element
Monotonic Stack & Queue Problems DSA practice problem on Onlearn.
Difficulty: easy.
Topics: What is the Next Smaller Element problem and what are the main approaches to solve it efficiently?, Arrays, Stack, Loops, Time Complexity, Space Complexity, Brute Force, Optimization, complexity analysis, brute force, stack, array, monotonic stack, traversal, Stack (LIFO), Algorithm Analysis.
Given an array of integers arr, for each element arr[i], find the Next Smaller Element to its right. The Next Smaller Element for an element x is the first element on the right side of x that is smaller than x. If no such element exists, consider it as 1. Input Specification: The first line contains a single integer N, the number of elements in the array. The second line contains N space separated integers, representing the elements of the array arr. Output Specification: Print N space separated integers, where the i th integer is the Next Smaller Element for arr[i]. Constraints: 1 <= N <= 10^5 0 <= arr[i] <= 10^9 Sample Test Cases: Input: 5 4 5 2 10 8 Output: 2 2 1 8 1 Explanation: For 4, the next smaller element is 2. For 5, the next smaller element is 2. For 2, there is no smaller element to its right, so 1. For 10, the next smaller element is 8. For 8, there is no smaller element to its right, so 1.