CODEWITHSUNDEEP
arraysalgorithmdata-structures
Watson
Watson

Reputation: 31

Find the last smaller or equal number for every element in the array?

I have been given an array. I need to find the last (right-most) smaller or equal number for every element in the array.

For example:

2 5 1 6 4 7

2 has last smaller or equal number 1,
5 has last smaller or equal number 4 and not 1, etc.

Another example:

5 100 8 7 6 5 4 3 2 1

Here, every element has last smaller or equal number 1. I know the naive approach, i.e. O(n²), but need a better approach.

Upvotes: 1

Views: 475

Answers (1)

arenard
arenard

Reputation: 672

You could go from right to left and build a min array of the minimum number until now. For your example 2 5 1 6 4 7, it would be: Start at rightmost position:

7
4 7    (4 < 7)
4 4 7  (6 > 4)
...

So the min array for your example would be: 1 1 1 4 4 7

Now for each query, you start at the same position in the min array and go right until finding a number which is greater:

For 2:

2 5 1 6 4 7
1 1 1 4 4 7
^
------^

First element greater than 2 is 4, so return number just before = 1

For 5:

2 5 1 6 4 7
1 1 1 4 4 7
  ^
----------^

First element greater than 5 is 7, so return number just before = 4

To find efficiently the first element greater for each element in the input array you can use upper_bound algorith (example in C++ http://www.cplusplus.com/reference/algorithm/upper_bound/) to find the first element which is greater

Upper_bound takes log(N) time, so overall time to process every element in input array is O(NlogN)

Memory complexity is linear for the min array

Upvotes: 5

Related Questions