# Developers Planet

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?

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
// 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 2016Viewed 2,220 timesVoted 8Answered 4 times Search Leave an answer ```
``` ```
``` ```
``` Quote of the day: live life .btn-primary{ background-color: #f44336 !important; border-color: #f44336 !important; } Devs Planet ® 2014-2016 www.devsplanet.com Devs Planet © all rights reserved Quick Actions Search // Used to toggle the menu on small screens when clicking on the menu button function myFunction() { var x = document.getElementById("navDemo"); if (x.className.indexOf("w3-show") == -1) { x.className += " w3-show"; } else { x.className = x.className.replace(" w3-show", ""); } } ```