Next Smaller Element

Problem Statement:

YOu are given an unsorted array, you need to find the next smaller element for all the elements.

Next smaller element for an item ‘x’ is the first smaller element on the right side of x in that array

Example

arr = [5, 9, 6, 3, 20]

Element        NSE
   5      -->   3
   9      -->   6
   6      -->   3
   3      -->   -1
   20     -->   -1

Solution

This problem can be solved using stack.

The solution for this problem is similar to next greater element.

Steps are as follows:

Push the first element into the stack.

Take the rest of the elements one by one and follow:

Store the current element as Next.

If the stack is not empty, then pop an element from the stack and check with the next. If it is smaller then next is the smaller element.

Continue this step till the popped element is greater than the next.

Once the loop is completed, then pop all the remaining elements from the stack and mark as -1.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 

using namespace std;
  
void display_next_smaller_element(int arr[], int n)
{
    stack<int> s;
 
    s.push(arr[0]);
 
    for (int i = 1; i < n; i++) 
    {
 
        if (s.empty()) 
        {
            s.push(arr[i]);
            continue;
        }
 
        while (s.empty() == false && s.top() > arr[i]) 
        {
            cout << s.top() << " --> " << arr[i] << endl;
            s.pop();
        }

        s.push(arr[i]);
    }
 
    while (s.empty() == false) 
    {
        cout << s.top() << " --> " << -1 << endl;
        s.pop();
    }
}
 
int main()
{
    int arr[] = { 4, 8, 5, 2, 25 };
    int n = sizeof(arr) / sizeof(arr[0]);
    display_next_smaller_element(arr, n);
    return 0;
}

Output:

8 --> 5
5 --> 2
4 --> 2
25 --> -1
2 --> -1