Algorithm: For each element of an array, find out the biggest value on its left side and less than itself

Question

For example, given an array:

[1, 2, 5, 4, 2, 6, 7, 3]

Find out each element's biggest value on its left side and less than itself (or -1 if no such element exists):

[-1,1, 2, 2, 1, 5, 6, 2]

What's the optimum algorithm? Is there an algorithm better than O(n*log(n))?

• RomanPerekhrest: what programming language?
• David: @RomanPerekhrest anyone you like c++, ruby, java..
• Codor: How would the O(n log n) algorithm look like? A naive algorithm would yield a runtime bound of O(n^2).
• Andrew: @David, I think its better if you provide your current solution to this problem and also move this question to Code Review site
• David: Sorry very the bad description of the problem..Thank you all for your advices. I'll read the guide for better questioning in the future. :)

Answer 1

Bruteforce algorithm is iterating the array, and search the visited elements one by one and compare with the current one. Thus this is O(n^2) algorithm.

The key to speed up the process is the search part. We have to take full advantage of what we already known, which is the elements we have visited.

Then the basic algorithm is like:

magic = new magic_data_structure
result = []
for x in input_array:
 y = magic.find_largest_but_less_than_current(x)
 result.push(y)
 magic.inesrt(x)

So we need a data structure which has complexity O(logn) of insert and search. This is typically a balanced search tree. We can use red-black tree for instance.

To make it simple, we can use set from c++ stl. See the following code for more details.

example link: http://ideone.com/5OIBCp

#include <bits/stdc++.h>
using namespace std;
using vi = vector <int>;
set <int> s;
vi foo(vi const &a) {
 vi ret;
 s.clear();
 for (auto const x: a) {
 auto it = s.lower_bound(x);
 if (it != begin(s)) {
 it = prev(it);
 ret.push_back(*it);
 } else {
 ret.push_back(-1);
 }
 s.insert(x);
 }
 return ret;
}
int main() {
 vi a = {1, 2, 5, 4, 2, 6, 7, 3};
 vi b = foo(a);
 for (auto x: b) printf("%d ", x); puts("");
 return 0;
}

---

https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

• David: That's awesome and clear! I don't expect such a quick and concise runnable code. :)
• vish4071: @David, welcome to SO. You should be expecting responses pretty quick from a community this large and talented.
• vish4071: @delta, A really nice c++ code you have written there. Much appreciated.