input:
5
4 2 1 5 3
6
5 6 2 3 1 7
Output
2 1 -1 3 -1
-1 2 -1 1 -1 -1
Explanation:
Testcase 1: Array elements are 4, 2, 1, 5, 3. Immediate smaller of 2 is immediate smaller of 4, 1 is immediate smaller of 2, no immediate smaller of 1, 3 is immediate smaller of 5, and no immediate smaller for last element exists. So ouput is : 2 1 -1 3 -1.
can you please tell me a solution better than o(n^2) complexity.??
hey @amanm2292, here is the link of the code http://suganyamurali.blogspot.com/2016/06/immediate-smaller-element.html
what if i want to iplement usinf stack?how can i do it logic?
Next Smaller Element
Given an array, print the Next Smaller Element (NSE) for every element. The Smaller smaller Element for an element x is the first smaller element on the right side of x in array. Elements for which no smaller element exist (on right side), consider next smaller element as -1.
Examples:
a) For any array, rightmost element always has next smaller element as -1.
b) For an array which is sorted in increasing order, all elements have next smaller element as -1.
c) For the input array [4, 8, 5, 2, 25}, the next smaller elements for each element are as follows.
Element NSE
4 --> 2
8 --> 5
5 --> 2
2 --> -1
25 --> -1
d) 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
hey @amanm2292, yes you can use stack. Here is the algo
-> Push the first element to stack.
-> from remaining elements ,pick one element one by one and perform follwing operations:
1.) Mark the current element as next.
2.) If stack is not empty, then pop an element from stack and compare it with next.
3.) If next is smaller than the popped element, then next is the next smaller element for the popped element.
-> Keep popping from the stack while the popped element is greater than next. next becomes the next smaller element for all such popped elements
-> After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them.