Find the max difference pair in the array

Question

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?

Answer 1

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;
}