You are given an array. You have to find the next smaller element for all elements. lets there is an element e you have to return the smaller first element of e. If you cannot find the first smaller element than this then simply return -1;
Example:
Input: [4,9,2,5,6,71]
output:[2,3,-1,-1,-1,-1]
Approach 1:
You can simply use two loops to find the answer. The first loop is to traverse the whole array. The second loop starts from the i+1 th element and checks for the nearest smaller element.
Code:
The time complexity of this problem is O(n^2). When all the elements are sorted that gives the worst case.
Approach 2:
You use a stack. and keep track of your nearest smaller element while traversing through right side.
Code:
Here your time complexity becomes O(n)
Photo by Oskar Yildiz on Unsplash
