Next Smaller Element

Posted: 27 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.
Approach 1

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 :

  1. Set all values of array ans as -1.
  2. 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.
  3. Return the array ans .
Try Problem