CSES Solutions – Nearest Smaller Values
Given an array arr[] of N integers, your task is to find for each array position (1-based indexing) the nearest position to its left having a smaller value.
Examples:
Input: N = 8, arr[] = {2, 5, 1, 4, 8, 3, 2, 5}
Output: 0 1 0 3 4 3 3 7
Explanation:
- For 1st element 2, there is no smaller element on the left, therefore print 0.
- For 2nd element 5, the 1st element = 2 is the smaller element on the left, therefore print 1.
- For 3rd element 1, there is no smaller element on the left, therefore print 0.
- For 4th element 4, the 3rd element = 1 is the smaller element on the left, therefore print 3.
- For 5th element 8, the 4th element = 4 is the smaller element on the left, therefore print 4.
- For 6th element 3, the 3rd element = 1 is the smaller element on the left, therefore print 3.
- For 7th element 2, the 3rd element = 1 is the smaller element on the left, therefore print 3.
- For 8th element 5, the 7th element = 2 is the smaller element on the left, therefore print 3.
Input: N = 5, arr[] = {1, 2, 3, 2, 1}
Output: 0 1 2 1 0
Explanation:
- For 1st element 1, there is no smaller element on the left, therefore print 0.
- For 2nd element 2, the 1st element = 1 is the smaller element on the left, therefore print 1.
- For 3rd element 3, the 2nd element = 2 is the smaller element on the left, therefore print 2.
- For 4th element 2, the 1st element = 1 is the smaller element on the left, therefore print 1.
- For 5th element 1, there is no smaller element on the left, therefore print 0.
Approach: To solve the problem, follow the below idea:
The problem can be solved using a Monotonic Stack to store the indices of elements of arr[]. Monotonic Stack stores all the elements in a certain order(increasing or decreasing). We will use Monotonic Stack such that it stores indices and as we move from top to bottom, we have indices of decreasing elements. Iterate over the array arr[] and for each item, keep popping the indices from the top of our stack as long as value at index = top is greater than or equal to our current item. This is because any value greater than our current value won’t be the answer for any future items, since our current item is smaller and is located further to the right in the array.
If we find a position such that value at that position is less than our current item, we’ll set the answer for our current position to this position. This is because our stack keeps the most recently added (rightmost) items at the top, so this position will be the rightmost position with a value less than our current item.
Finally, we’ll add the current position to the stack.
Step-by-step algorithm:
- Initialize a stack, say prevSmaller that stores the indices of previous elements such that if we move from top to bottom, we have all the indices of decreasing elements.
- Iterate over all the indices from 0 to N – 1,
- Keep popping the indices from the top of our stack till value at index = top is >= current element.
- After popping, if the stack is empty then print 0.
- Otherwise, print the top of the stack + 1 (1-based indexing).
- Push the current index to the stack.
Below is the implementation of the algorithm:
C++
#include <bits/stdc++.h> #define ll long long int using namespace std; // function to find the position of left smaller element for // all indices void solve(vector<ll>& arr, ll N) { // Stack to store indices of previous smaller elements stack<ll> prevSmaller; for ( int i = 0; i < N; i++) { // Pop from the stack till there are elements in the // stack and the element at index = // prevSmaller.top() is greater than the current // element while (!prevSmaller.empty() && arr[prevSmaller.top()] >= arr[i]) { prevSmaller.pop(); } // If there is no position with smaller element on // the left side if (prevSmaller.empty()) cout << 0 << " "; // If there is a position with smaller element on // the left side, print it else cout << prevSmaller.top() + 1 << " "; // Push the current position to the stack prevSmaller.push(i); } } int main() { // Sample Input ll N = 8; vector<ll> arr = { 2, 5, 1, 4, 8, 3, 2, 5 }; solve(arr, N); // your code goes here return 0; } |
Java
/*code by flutterfly*/ import java.util.*; public class Main { // function to find the position of left smaller element for all indices static void solve(List<Long> arr, int N) { // Stack to store indices of previous smaller elements Stack<Integer> prevSmaller = new Stack<>(); for ( int i = 0 ; i < N; i++) { // Pop from the stack till there are elements in the // stack and the element at index = prevSmaller.top() is greater than the current element while (!prevSmaller.empty() && arr.get(prevSmaller.peek()) >= arr.get(i)) { prevSmaller.pop(); } // If there is no position with smaller element on the left side if (prevSmaller.empty()) System.out.print( 0 + " " ); // If there is a position with smaller element on the left side, print it else System.out.print(prevSmaller.peek() + 1 + " " ); // Push the current position to the stack prevSmaller.push(i); } } public static void main(String[] args) { // Sample Input int N = 8 ; List<Long> arr = Arrays.asList(2L, 5L, 1L, 4L, 8L, 3L, 2L, 5L); solve(arr, N); } } |
Python
# code by flutterfly # function to find the position of left smaller element for # all indices def solve(arr): # Stack to store indices of previous smaller elements prev_smaller = [] for i in range ( len (arr)): # Pop from the stack till there are elements in the # stack and the element at index = # prev_smaller[-1] is greater than the current # element while prev_smaller and arr[prev_smaller[ - 1 ]] > = arr[i]: prev_smaller.pop() # If there is no position with smaller element on # the left side if not prev_smaller: print 0 , # If there is a position with smaller element on # the left side, print it else : print prev_smaller[ - 1 ] + 1 , # Push the current position to the stack prev_smaller.append(i) # Sample Input arr = [ 2 , 5 , 1 , 4 , 8 , 3 , 2 , 5 ] solve(arr) |
C#
//code by flutterfly using System; using System.Collections.Generic; class Program { // function to find the position of left smaller element for // all indices static void Solve(List< long > arr) { // Stack to store indices of previous smaller elements Stack< long > prevSmaller = new Stack< long >(); for ( int i = 0; i < arr.Count; i++) { // Pop from the stack till there are elements in the // stack and the element at index = // prevSmaller.Peek() is greater than the current // element while (prevSmaller.Count > 0 && arr[( int )prevSmaller.Peek()] >= arr[i]) { prevSmaller.Pop(); } // If there is no position with smaller element on // the left side if (prevSmaller.Count == 0) Console.Write( "0 " ); // If there is a position with smaller element on // the left side, print it else Console.Write(prevSmaller.Peek() + 1 + " " ); // Push the current position to the stack prevSmaller.Push(i); } } static void Main( string [] args) { // Sample Input List< long > arr = new List< long > { 2, 5, 1, 4, 8, 3, 2, 5 }; Solve(arr); } } |
Javascript
//code by flutterfly // function to find the position of left smaller element for all indices function solve(arr) { // Stack to store indices of previous smaller elements let prevSmaller = []; for (let i = 0; i < arr.length; i++) { // Pop from the stack till there are elements in the stack and the element at index = prevSmaller[prevSmaller.length - 1] is greater than the current element while (prevSmaller.length > 0 && arr[prevSmaller[prevSmaller.length - 1]] >= arr[i]) { prevSmaller.pop(); } // If there is no position with smaller element on the left side if (prevSmaller.length === 0) process.stdout.write( "0 " ); // If there is a position with smaller element on the left side, print it else process.stdout.write(prevSmaller[prevSmaller.length - 1] + 1 + " " ); // Push the current position to the stack prevSmaller.push(i); } } // Sample Input const N = 8; const arr = [2, 5, 1, 4, 8, 3, 2, 5]; solve(arr, N); |
0 1 0 3 4 3 3 7
Time Complexity: O(N), where N is the size of arr[].
Auxiliary Space: O(N)
Contact Us