62. Smallest number on left

Topic :

stack

Difficulty :

medium

Problem Link :

problem statement

Given an array, a of integers of length n, find the nearest smaller number for every element such that the smaller element is on the left side. If no small element is present on the left print -1.

Example 1:

Input: n = 3
a = {1, 6, 2}
Output: -1 1 1
Explaination: There is no number at the 
left of 1. Smaller number than 6 and 2 is 1.

Example 2:

Input: n = 6
a = {1, 5, 0, 3, 4, 5}
Output: -1 1 -1 0 3 4
Explaination: Upto 3 it is easy to see 
the smaller numbers. But for 4 the smaller 
numbers are 1, 0 and 3. But among them 3 
is closest. Similary for 5 it is 4.

Your Task:
You do not need to read input or print anything. Your task is to complete the function leftSmaller() which takes n and a as input parameters and returns the list of smaller numbers.

Constraints:
1 ≤ n ≤ 10000
0 ≤ a[i] ≤ 104

solution

TIME COMPLEXITY : O(N)

SPACE COMPLEXITY: O(N)

import java.io.*;
import java.util.*;
 class PreviousSmallerElement
{
    public static void main(String args[]){
      int a[]={1, 5, 0, 3, 4, 5};
      int n=a.length;
      System.out.println(leftSmaller(n,a));
    }
    static List<Integer> leftSmaller(int n, int a[])
    {
      List<Integer>ans= new ArrayList<>();
      Stack<Integer> stack=new Stack<>();//create a stack
      for(int ele:a){
         //if the element at the top of the stack is greater than the curr ele
         //remove that element from the stack
         while(!stack.isEmpty() && stack.peek()>=ele){
             stack.pop();
         }
         //if there are no elements in the stack 
         //it means there are no elements that are smaller than the curr element on its left
         if(stack.isEmpty())
          ans.add(-1);
         else // add the element at the top of the stack 
          ans.add(stack.peek());
         
         stack.push(ele);//push the curr ele to the stack
      }
      return ans;
    }
}