64. Next Smaller Element

Topic :

stack

Difficulty :

medium

Problem Link :

problem statement

Given an array, print the Next Smaller Element (NSE) for every element. The NSE for an element x is the first smaller element on the right side of x in the array. Elements for which no smaller element exist (on the right side), consider NSE as -1.

Examples:

For any array, the rightmost element always has NSE as -1.
For an array that is sorted in increasing order, all elements have NSE as -1.
For the input array [4, 8, 5, 2, 25}, the NSE for each element is as follows.

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

For the input array [13, 7, 6, 12}, the next smaller elements for each element are as follows.

  Element        NSE
   13      -->    7
   7       -->    6
   6       -->   -1
   12      -->   -1

solution

import java.io.*;
import java.util.*;
class NextSmallerElement
{
  public static void main(String args[]){
      int a[]={1, 5, 0, 3, 4, 2};
      int n=a.length;
      System.out.println(nextSmaller(n,a));
    }
    static List<Integer> nextSmaller(int n, int a[])
    {
      List<Integer>ans= new ArrayList<>();
      Stack<Integer> stack=new Stack<>();
      for(int i=a.length-1;i>=0;i--){
         int ele=a[i];
         while(!stack.isEmpty() && stack.peek()>=ele){
             stack.pop();
         }
        
         if(stack.isEmpty())
          ans.add(-1);
         else 
          ans.add(stack.peek());
         
         stack.push(ele);
      }
      Collections.reverse(ans);
      return ans;
    }
}