Monotonic Pair - Codility

Question

I was just at Codility, and ran into a task for which I can't find a solution in targeted O(n) efficiency; my solution runs for O(n2). I would be very pleased if someone could just give me a hint on how to get it run faster. Here is the task.

A non-empty zero-indexed array A consisting of N integers is given.

A monotonic_pair is a pair of integers (P, Q), such that 0 ≤ P ≤ Q < N and A[P] ≤ A[Q].

The goal is to find the monotonic_pair whose indices are the furthest apart. More precisely, we should maximize the value Q − P. It is sufficient to find only the distance.

For example, consider array A such that:

A[0] = 5
A[1] = 3
A[2] = 6
A[3] = 3
A[4] = 4
A[5] = 2

There are eleven monotonic_pairs: (0,0), (0, 2), (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 3), (3, 4), (4, 4), (5, 5). The biggest distance is 3, in the pair (1, 4).

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty zero-indexed array A of N integers, returns the biggest distance within any of the monotonic_pairs.

For example, given:

A[0] = 5
A[1] = 3
A[2] = 6
A[3] = 3
A[4] = 4
A[5] = 2

the function should return 3, as explained above.

Assume that:

N is an integer within the range [1..300,000]; each element of array A is an integer within the range [−1,000,000,000..1,000,000,000]. Complexity:

expected worst-case time complexity is O(N); expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments). Elements of input arrays can be modified.

And my 1st idea solution (runs in O(n2)):

    public static int solution(int[] A) {
    int max = 0;
    for(int i=0; i<A.length-1; i++) {
        for(int j=i+1; j<A.length; j++) {
            if(A[j] >= A[i] &&
                    (j - i) >= max) {
                max = j - i;
            }
        }
    }
    return max;
}

Answer 1

MarcinLe's is better than n^2, but still runs in nlogn. You can optimize by not doing your logn lookup every time. Instead, iterate forward over your max array and your input A[] array at the same time to guarantee linear time.

int[] top = new int[A.length];
int max = -Integer.MAX_VALUE;
for (int i=A.length-1; i>=0; i--) {
    if (A[i] > max) max = A[i];
    top[i] = max;
}

int best = 0;
int curMaxIndex = 0;
for (int i=0; i<A.length; i++) {
    while(curMaxIndex < top.length && top[curMaxIndex] >= A[i])
        curMaxIndex++;
    if((curMaxIndex - 1 - i) > best)
        best = curMaxIndex - 1 - i
}

return best; 

Answer 2

Create a temporary array containing maximum values in descending order:

int[] top = new int[A.length];
int max = -Integer.MAX_VALUE;
for (int i=A.length-1; i>=0; i--) {
    if (A[i] > max) max = A[i];
    top[i] = max;
}

so you can quickly find them with binary search:

int find(int[] t, int min) {
    int s = 0;
    int e = t.length-1;

    if (t[e] >= min) return e;

    while (true) {
        int x = (s+e) / 2;
        if (x == t.length-1) return t.length-1;
        if (t[x] >= min && t[x+1] < min) return x;

        if (t[x] < min) e = x;
        else s = x;
    }
}

And you got a solution:

int best = 0;
for (int i=0; i<A.length; i++) {
    int c = find(top, A[i]) - i;
    if (c > best) best = c;
    if (best >= A.length-i) return best;
}

return best;

Answer 3

There is also another algorithm, based on finding maximum distance between pairs (sorry, PHP), it also has O(n2) complexity:

function solution($a) {

    $length = count($a);

    for($max = $length-1; $max > 0; $max-- ) {
        for($i = 0; $i < $length - $max ; $i++) {
            if ($a[$i] <= $a[$i+$max]) {
                return $max;
            }    
        }
    }

    return 0;
}