Question

Given an array, find out the last smaller element for each element

Answer 1

Answer:

Given an array find the last smaller element's index in array for each element.

For example, suppose the given array is {4,2,1,5,3}. Then last smaller element for each element will be as follows.

4->3

2->1

1->Null

5->3

3->Null

Notice for 1st pair 4->3, 3 is the last element in array smaller than 4.

The resultant/output array would have indexes not the elements themselves. Result would be {4,2,-1,4,-1}

I was asked this question in an interview, but i couldn't think of a solution better than the trivial O(n^2) solution.

Explanation: