JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
How to find maximum element on left hand side of an element which is smaller than the element in an array? | Reply
Suppose I have an array of integers like this:

{ 3, 1, 6, 8, 2, 0, 1 }

I need to find the maximum element on the left hand side of each element which is smaller than the element, or print -1 if that maximum element doesn't exist. So, solution for this problem will be:

{ -1, -1, 3, 6, 1, -1, 0 }

I can solve this in O(n^2) using two loops. Inner loop will find maximum element which is smaller than the given element. But is there any better approach to solve this?
Re: How to find maximum element on left hand side of an element which is smaller than the element in an array? (response to post by d@rk_sh@dow) | Reply
You can use BIT for O(n*log(n)) complexity.
RSS