Next Smaller Element
You are given an array 'ARR' of integers of length N. Your task is to find the next smaller element for each of the array elements.

Next Smaller Element for an array element is the first element to the right of that element which has a value strictly smaller than that element.

If for any array element the next smaller element does not exist, you should print -1 for that array element.

For Example:

If the given array is [ 2, 3, 1], we need to return [1, 1, -1]. Because for 2, 1 is the Next Smaller element. For 3, 1 is the Next Smaller element and for 1, there is no next smaller element hence the answer for this element is -1.

Input Format:

The first line of input contains an integer ‘T’ which contains the number of test cases. The first line of each test case contains an integer 'N' denoting the number of elements in the array 'ARR'. The second line of each test case contains 'N' space-separated integers denoting the array 'ARR'.

Output Format:

For each test case, print a single line containing 'N' space-separated integers denoting the value of Next Smaller Element for each of the 'N' array elements. The output for each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Next Smaller Element

You are given an array 'ARR' of integers of length N. Your task is to find the next smaller element for each of the array elements.

Next Smaller Element for an array element is the first element to the right of that element which has a value strictly smaller than that element.

If for any array element the next smaller element does not exist, you should print -1 for that array element.

For Example:

If the given array is [ 2, 3, 1], we need to return [1, 1, -1]. Because for  2, 1 is the Next Smaller element. For 3, 1 is the Next Smaller element and for 1, there is no next smaller element hence the answer for this element is -1.

Input Format:

The first line of input contains an integer ‘T’ which contains the number of test cases.

The first line of each test case contains an integer 'N' denoting the number of elements in the array 'ARR'.

The second line of each test case contains 'N' space-separated integers denoting the array 'ARR'.

Output Format:

For each test case, print a single line containing 'N' space-separated integers denoting the value of Next Smaller Element for each of the 'N' array elements.

The output for each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10 ^ 5
0 <= ARR [i] <= 10 ^ 9

Time Limit: 1sec.

Accepted Answer

I used stack to solve this problem. Here we maintain items in increasing order in the stack (instead of decreasing in next greater element problem).

Push the first element to stack.
Pick rest of the elements one by one and follow following steps in loop.
Mark the current element as next.
If stack is not empty, then compare next with stack top. If next is smaller than top then next is the NSE for the top. Keep popping from the stack while top is greater than next. next becomes the NSE for all such popped elements
Push next into the stack
After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them.

Accepted Answer

Brute Force Approach

The idea is to find the Next Smaller Element for each array element one by one. To find the Next Smaller for an array element we will start moving to the right of that element and will try to find the first element having a value smaller than that element and set the Next Smaller Element as that element and end our search. If we reach the end of the array without finding any such element then we will set the next smaller element as -1 for that element.

Let ans be an array of length N that stores the Next Smaller Elements.

Steps :

Set all values of array ans as -1.
Iterate from i = 0 to N - 1
- Iterate from j = i + 1 to N -1
  - If ARR [i] is greater than ARR [j]then set the value of ans [i] to ARR [j] and break the loop.
Return the array ans .

Space Complexity: O(1)Explanation:

O(1), as we are using constant extra space.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the number of elements in the array.

We are traversing the array. And for each element we are checking all the elements to the right of it. Thus, at most ‘N’ searches for each index. Hence, the total time complexity is O(N^2).

C++ (g++ 5.4)

/*

    Time Complexity: O(N ^ 2)

    Space Complexity: O(1)



    Where N denotes the number of elements in the array.

*/



vector nextSmallerElement(vector & arr, int n) 

{

    // Defining the vector to store next smaller elements for the array.

    vector ans(n);



    // Iterating through all the array elements and finding next smaller element for each element.

    for (int i = 0; i < n; i++) 

    {

        // Initializing the next smaller element as -1.

        ans[i] = -1;



        // Moving to the right of the element.

        for (int j = i + 1; j < n; j++)

        {

            // Checking for the next smaller element.

            if (arr[i] > arr[j])

            {

                ans[i] = arr[j];

                break;

            }

        }



    }



    // Returning the final vector after all the iterations.

    return ans;

}

Java (SE 1.8)

/*

    Time Complexity: O(N ^ 2)

    Space Complexity: O(1)



    where N denotes the number of elements in the array.

*/



import java.util.ArrayList;



public class Solution{

    public static ArrayList nextSmallerElement(ArrayList arr, int n) {

        ArrayList ans = new ArrayList();



         // Iterating through all the array elements and finding next smaller element for each element.

   		 for (int i = 0; i < n; i++) {



       	 	// Initializing the next smaller element as -1.

        	ans.add(-1);



        	// Moving to the right of the element.

        	for (int j = i + 1; j < n; j++) {



            	// Checking for the next smaller element.

            	if (arr.get(i) > arr.get(j)) {

					ans.set(i, arr.get(j));

                	break;

            	}

        	}	

    	}



        return ans;

    }

}

Python (3.5)

'''

    Time Complexity: O(N ^ 2)

    Space Complexity: O(1)



    Where N denotes the number of elements in the array.

'''



def nextSmallerElement(arr, n):



    # Defining the list to store next smaller elements for the array.

    ans = [0 for i in range(n)]



    # Iterating through all the array elements and finding next smaller element for each element.

    for i in range(n):



        # Initializing the next smaller element as -1.

        ans[i] = -1



        # Moving to the right of the element.

        for j in range(i + 1, n):



            # Checking for the next smaller element.

            if(arr[i] > arr[j]):

                ans[i] = arr[j]

                break



    # Returning the final vector after all the iterations

    return ans

Accepted Answer

Optimized Approach using Stack

The idea is to find the Next Smaller Element for each of the N array elements in one iteration of the array by using a stack. Our approach is to traverse the array from right to left and for each array element we will first pop all such elements that are currently at the top of stack and having a value greater than or equal to the current element. Now we will set the Next Smaller Element as the element at the top of the stack if the stack is non-empty otherwise we will set it as -1. Now we will push that element into the stack and move ahead.

Let ans be an array of length N that stores the Next Smaller Elements.

Steps :

Create an empty stack of type integer and push -1 to it .
Traverse the array from backwards and for every element at index 'i’,
- We will pop the elements from the stack till we get the smaller element on top of the stack from the current element i.e. ARR[i] and that element will be the answer for the current element.Store the next smaller element in the array ans.
- Push the current element of the array into the stack.
Return the array ans.

This algorithm works because whenever we push an element to the stack, we know its value is greater than every element present in the stack. As we visit an array element, we know that if it's value is less than any item in the stack, it must be smaller than the element at the top of the stack because it is the largest item of the stack. Therefore we need not to do any kind of searching on the stack and we can just consider the last item every time.

Space Complexity: O(n)Explanation:

O(N), where N is the number of elements in the array.

The size of the stack used can be at most ‘N’. Hence, the space complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of elements in the array.

We are traversing the array only once. Also, each element can be pushed into the array once. Thus the overall time complexity is O(N).