Program for Next Smaller Element | C++ Solution.

Problem:

You are given an array of integers of size n. Your task is to print the next smaller element for each element present in the given array and if no smaller element is present for any element then print -1 for that element. 

The Next Smaller Element for an array element (x) is the first smaller element on the right side of that element (x) in the array. If you reach the last element of the array in that case you cannot see any element on the right side so in that case print -1 if no Next Smaller Element is present. 

You have to store all Next Smaller Elements in an array of n sizes and print them.   

Input: arr = [ 2, 3, 1, 5, 9, 4 ]
Output: ans = [ 1, 1, -1, 4, 4, -1 ]

Explanation:
For 2, the next smaller element present on the right side of 2 in the array is 1.
For 3, the next smaller element present on the right side of 3 in the array is 1.
For 1, there is no next smaller element so you can print -1.
For 5, the next smaller element present on the right side of 5 in the array is 4.
For 9, the next smaller element present on the right side of 9 in the array is 4.
For 4, there is no element present on the right side of 4 so you can print -1. 

I hope that the problem statement is now clear to you, so let's start thinking about different approaches to solve this problem.

Approach 1: Using two nested loops. 

Starting from the left side of the array, the outer loop will pick each element from the array one by one and the inner loop will check if any smaller element is present for the element picked by the outer loop on the right side of that element. If the smaller element is found then store that element in an array and if no smaller element is found then store -1. 

#include <bits/stdc++.h>
using namespace std;

void nextSmallerElement(int arr[], int n, int ans[])
{
    for (int i = 0; i < n; i++)
    {
        int num = -1;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[i])
            {
                num = arr[j];
                break;
            }
        }
        ans[i] = num;
    }
}

int main()
{
    int arr[] = {2, 3, 1, 5, 9, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    int ans[size];

    nextSmallerElement(arr, size, ans);
    for (int i = 0; i < size; i++)
    {
        cout << ans[i] << " ";
    }
}

Output:

1 1 -1 4 4 -1

• Time Complexity: O(n^2)
• Space Complexity: O(1)

Approach 2: Using Stack Data Strcuture.

As you can see that the above approach of solving the problem using two nested loop is not a good approach for solving this problem because it increases your time complexity to O(n^2). You can more efficiently solve the problem using Stack data structure and its property. 

Create a Stack and push -1 initially and now -1 is present at the top of stack. Now approach the given array element from the right hand side and whenever you pick one element x , check the topmost element of the stack. If top element is smaller than the element x you just picked, store the topmost element of stack into your ans array and push the picked element x. 

If you get a situation in which the topmost element is not smaller than element x start popping out elements from the stack until a topmost element smaller element than x. When you find that element, store that element into ans array and push the x into the stack.

#include <bits/stdc++.h>
using namespace std;

void nextSmallerElement(int arr[], int n, int ans[])
{
    stack<int> st;
    st.push(-1);
    for (int i = n - 1; i >= 0; i--)
    {
        int curr = arr[i];
        while (st.top() >= curr)
        {
            st.pop();
        }
        ans[i] = st.top();
        st.push(curr);
    }
}
int main()
{
    int arr[] = {2, 3, 1, 5, 9, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    int ans[size];

    nextSmallerElement(arr, size, ans);
    for (int i = 0; i < size; i++)
    {
        cout << ans[i] << " ";
    }
}

Output:

1 1 -1 4 4 -1 

• Time Complexity: O(n)
• Space Complexity: O(n)