Is it possible to find the largest drop between two numbers in an array in less than O(n²) complexity?

Question

i have an array full of numbers. i need to find the maximum different between 2 numbers but the biggest number is before the smallest number in the array.

public static int maximalDrop (int [] a)

For example:

for the array 5, 21, 3, 27, 12, 24, 7, 6, 4 the result will be 23 (27 - 4)

for the array 5, 21, 3, 22, 12, 7, 26, 14 the result will be 18 (21 - 3)

My solution is take the first element in the array (this number will be the big) and check the the difference between this number and all other numbers in the array and after that do the same thing but with the next number in the array and of course compare the difference and return the biggest one. i thing that my solution is O(n²) so can i do that in less ?

Answer 1

Unless I misunderstand the question I believe you can do this in one pass of the array. You just need to keep track of the maximum value and maximum difference you have seen so far. As you go through the array calc the difference between the current number and the maximum seen so far.

So for your second example 5, 21, 3, 22, 12, 7, 26, 14

1: 5 is first value so set maximum to 5
2: 21 > 5 so reset maximum
3: 21 - 3 = 18
4: 22 > 21 so reset maximum
5: 22 - 12 = 10
6: 22 - 7  = 15
7: 26 > 22 so reset maximum
8: 26 - 14 = 12

As the smaller number comes after the larger when you find a new maximum any smaller number beyond it in the array needs to be subtracted from this new maximum.

The answer required is the maximum value seen during this process - in this case the 18 that is calulated in step 3.

Answer 2

Try this:

public static int maximalDrop (int[]a)
{
    int max= a[0];
    int dif= 0;
    for (int i=0; i<a.length; i++)
    {
        if(a[i]>max){
            max=a[i];
            if (dif<max-a[i+1])
            {
             dif=max-a[i+1];   
            }
        }
    }
    return dif;    
}

Answer 3

Well, I'm not sure whether my understanding about this question is correct or not. However, I think you only need to keep track of the largest value you have already visited so far and the drop value. Consider this, if the largest drop made by a-b; and there is another value c before b which is larger than a, then c-b definitely larger than a-b, then the largest drop should be c-b. While, even though there will be a larger number replacing the max value later on, it won't change the drop value unless it can make a larger drop.

This code maybe work, it's in java: So the time cost is O(n). If I misunderstood some concepts, please let me know.

public int findDrop(int[] ar){ int max = ar[0]; int drop = 0; for(int i=1;i<ar.length;i++){ if(ar[i] > max){ max = ar[i]; } else { if(max - ar[i] > drop){ drop = max - ar[i]; } } } return drop; }

Answer 4

O(N) solution

public static int findMaxDrop(int[] arr){
    int maxSoFar=0;
    int currDrop=0;
    int maxDrop=0;

    for(int i=0;i<=arr.length-1;i++){
        if(arr[i] > maxSoFar){
            maxSoFar=arr[i];
        }else{
            currDrop = maxSoFar-arr[i];
            maxDrop=Math.max(currDrop, maxDrop);
        }
    }
    return maxDrop;
}

Answer 5

You should only need a minor tweak to merge sort to do this in O(n log n)!

Answer 6

can be done in O(n) :

1. merge sort the list
2. get the minimum and the maximum items and calculate the diff between them.