Solving the max distance problem

Правка en3, от krngrvr09, 2016-07-03 10:35:58

Hey, so I recently started solving the problem of max distance in an array.

The problem statement is this:

Given an array A of integers, find the maximum of j - i subjected to the constraint of A[i] <= A[j].

My approach to this is the following:

Consider the index pairs: (1,n-1),(2,n-1),(3,n-1)......(n-1,n-1)
                    (1,n-2),(2,n-2),(3,n-2)...(n-2,n-2)
                    and so on...
While looping through these pairs keep storing the max distance and skip the rows where a result greater than max distance is not possible. So, if index pair (1,n-1) generates a result, then all rows below that are not capable of generating a solution greater than that.

Here is the code. A is the given array as a vector<int>.

    int si=0;
    int ei=A.size()-1;
    int res=-1;
    while(ei>=0){
        int temp=si;
        while(((ei-temp)>res)&&(ei>=temp)){
            if(A[ei]>=A[temp]){
                res=ei-temp;
            }
            temp++;
        }
        ei--;
    }
    cout<<res<<endll;

I am solving this problem on interview bit[link] and it is showing a runtime error. Can somebody point out the flaw in this approach/code. I am not able to figure it out.

Thanks.

-----EDIT----- It turned out that I was supposed to solve it in O(nlogn). I think Interviewbit shows Runtime error, even for TLE. I am not sure if this is actually the case, but it has been suggested by many users.

I then solved the problem in O(n) time as suggested by the geeksforgeeks post.

Теги help needed, algorithm

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский krngrvr09 2016-07-03 10:35:58 398 Turns out runtime error was actually a TLE. Weird, but that's the case for now.
en2 Английский krngrvr09 2016-07-02 14:34:07 42
en1 Английский krngrvr09 2016-07-02 14:32:32 1322 Initial revision (published)