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?

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