CODEWITHSUNDEEP
c++algorithm
user4016367
user4016367

Reputation: 481

codility MaxDistanceMonotonic, what's wrong with my solution

Question:

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:

int solution(vector &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.

Here is my solution of MaxDistanceMonotonic:

    int solution(vector<int> &A) {

    long int result;

    long int max = A.size() - 1;
    long int min = 0;

    while(A.at(max) < A.at(min)){
        max--;
        min++;
    }

    result = max - min;

    while(max < (long int)A.size()){
        while(min >= 0){
            if(A.at(max) >= A.at(min) && max - min > result){
                result = max - min;    
            }
        min--;
        }
    max++;
    }

    return result;
}

And my result is like this, what's wrong with my answer for the last test:

enter image description here

Upvotes: 1

Views: 2283

Answers (1)

IVlad
IVlad

Reputation: 43467

If you have:

0  1 2  3  4  5
31 2 10 11 12 30

Your algorithm outputs 3, but the correct answer is 4 = 5 - 1.

This happens because your min goes to -1 on the first full run of the inner while loop, so the pair (1, 5) will never have the chance to get checked, max starting out at 4 when entering the nested whiles.

Note that the problem description expects O(n) extra storage, while you use O(1). I don't think it's possible to solve the problem with O(1) extra storage and O(n) time.

I suggest you rethink your approach. If you give up, there is an official solution here.

Upvotes: 0

Related Questions