For example, I have an
input array
[1,3,5,6,4,8,4,3,2,1]
the output should be [-1 , 1, 3, 5, 3 , 6, 3, 1, 1, -1]
Explanation: let's keep the first element as -1, as there is no smaller one previous to that.
In index '1' the previous smaller element to 3 needs to be stored. i.e 1.
In index '2' the previous smaller element to 5 needs to be stored. i.e 3. & so on...
I know I can solve this problem in O(n2) complexity. But I Would like to solve this in O(n) complexity. I have tried, but I am unable to do it.
Please help me to solve this problem. Thanks in Advance.
O(n) is probably impossible, but I can give you O(n log n) approach. Create a balanced BST (set/dictionary structure in most of programming languages). You can now easily find the largest number smaller than x by traversing a tree.
Set/dictionary structure often have a built-in function called upper bound, that find you smallest element larger than x (or largest smaller if you decide to change sorting order). You may also use that.
All you need to do is:
For each value v in the array:
find the largest number smaller than v in BST,
insert v into BST