CODEWITHSUNDEEP
arraysalgorithm
David
David

Reputation: 17

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

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))?

Upvotes: 0

Views: 54

Answers (1)

delta
delta

Reputation: 3818

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

Upvotes: 3

Related Questions