Home Ask Login Register

Developers Planet

Your answer is one click away!

Jason Z February 2016

Find the max difference pair in the array

I am working on some kata but I cannot pass all the test cases.

So the situation is:

Given any array, such as this array: int[] a = {2, 3, 10, 2, 4, 8, 1}, find the max difference pair in the array, in the meantime make sure the larger value is at the higher index than the lower value.

In this example: 10 is the largest element, 1 is the smallest, since 10 is at index 2, 1 is at index 6, so it does not count because the larger pair is at a lower index. So the correct answer is a[0], and a[2], max different is 10-2.

Other requirement is array size N is between 1 and 1_000_000, any given a[i] is between -1_000_000 and 1_000_000

I wrote code like this:

static int maxDifference(int[] a) {
    //test array size
    if (a.length < 1 || a.length > 1_000_000) return -1;

    int[] oldArr = Arrays.copyOf(a, a.length);
    Arrays.sort(a);
    int max = a[a.length - 1];
    if (max > 1_000_000 || a[0] < -1_000_000) return -1;

    int min = max;
    for (int i = 0; i < oldArr.length; i++) {
        if (oldArr[i] < max) {
            min = Math.min(min, oldArr[i]);
        }
        if (oldArr[i] == max) break;
    }
    int result = min == max ? -1 : max - min;
    return result;
}

My logic is pretty much make a copy of the array and then sort the array, then loop it though, keep a pointer for max and min values, then get the result.

What is troubling me is I only know there are some test cases I didn't pass, but no hints on why it didn't pass. Can anyone give me some advise and what I may missing in this helper method?

Answers


Neuron February 2016

If performance is not an issue (what I assume, since you are sorting the array which is probably not the most efficient implementation), this simple but easily readable piece of code should do the trick:

public static int maxDifference(int[] a) {
    int biggestDifference = -1;
    if(a.length > 1_000_000){
        return -1;
    }
    for (int i = 0; i < a.length-1; i++) {
        if(Math.abs(a[i]) > 1_000_000){
            return -1;
        }
        for (int j = i+1; j < a.length; j++) {
            int difference = a[j] - a[i];
            if(difference > biggestDifference){
                biggestDifference = difference;
            }
        }
    }
    return biggestDifference;
}


Amit February 2016

Basically you need to keep track of the minimum value found so far and the maximum diff found so far:

static int maxDifference(int[] a) {
    int minimum, diff = -1;
    if(a.length == 0) {
        return -1;
    }
    minimum = a[0];
    for (int i = 1; i < a.length; i++) {
        diff = Math.max(diff, a[i] - minimum);
        minimum = Math.min(minimum, a[i]);
    }
    return diff;
    // depending on interpretation of requirements, above line might be wrong
    // Instead, use:
    // return diff > 0 ? diff : -1;
}


MT0 February 2016

This finds the local minima and maxima and keeps track of the global minima and the position of the current maximum difference.

import java.util.Arrays;

public class MaxDifference {
    private static long difference(
            final int[] array,
            final int minPos,
            final int maxPos
    )
    {
        assert( minPos < maxPos );
        assert( array[minPos] < array[maxPos] );
        return ( (long) array[maxPos] ) - ( (long) array[minPos] );
    }

    public static int[] maxDifference( final int[] array ){
        if ( array == null|| array.length < 2 )
            return null;

        // Position of global minima.
        int minimaPos                 = 0;
        // Value of global minima.
        int minimaValue               = array[0];
        // Position of minima for current maximum difference.
        int minimaPosForMaxDifference = 0;
        // Position of maxima for current maximum difference.
        int maximaPosForMaxDifference = -1;
        // Current maximum difference.
        long maxDifference            = -1;
        // Current position
        int pos                       = 0;


        while ( pos < array.length - 1 ){
            // Find the local minima
            while( pos < array.length - 1 && array[pos] > array[pos + 1])
            {
                pos++;
            }
            // Test if the local minima is the current global minima.
            if ( array[pos] < minimaValue )
            {
              minimaPos   = pos;
              minimaValue = array[pos];
            }

            // Find the local maxima
            while( pos < array.length - 1 && array[pos] <= array[pos + 1])
            {
                pos++;
            }

            if ( pos > minimaPos )
            {
                long diff = difference( array, minimaPos, pos );
                if ( diff > maxDifference )
                {
                    minim 


Konstantinos Chalkias February 2016

Just to note that Amit's solution works either working with minimum or maximum. The nice property using maximum is that you only need one extra function (Math.Max). For the unbelievers, just perform a Unit test and check. In any case, this is indeed solvable in O(n).

//using minimum (Amit's solution - vote him up!)
static int maxDifferenceWithMin(int[] a) {
    int minimum, diff = -1;
    if (a.length == 0) {
        return -1;
    }
    minimum = a[0];
    for (int i = 1; i < a.length; i++) {
        diff = Math.max(diff, a[i] - minimum);
        minimum = Math.min(minimum, a[i]);
    }
    return diff;
}

//using maximum
static int maxDifferenceWithMax(int[] a) {
    int maximum, diff = -1;
    if(a.length == 0) {
        return -1;
    }
    maximum = a[a.length - 1];
    for (int i = a.length - 1; i >= 0; i--) {
        diff = Math.max(diff, a[i] - maximum);
        maximum = Math.max(maximum, a[i]);
    }
    return diff;
}

Post Status

Asked in February 2016
Viewed 2,220 times
Voted 8
Answered 4 times

Search




Leave an answer


Quote of the day: live life