# Find the 2 distinct highest values in an array

I want to know if there is a way to improve my code. It finds the two highest values in an array, and these numbers need to be distinct.

I don't want to sort the values; I just want to find them.

My idea is to create a new array if the length is even and compare the pair of values to find the minimum and maximum values.

So, later, I find the second highest value.

package doze;

public class Elementos {

public int maxValue(int array[], int arrayLength) {

arrayLength = array.length;

if ((arrayLength % 2) > 0) {
arrayLength++;
int aux[] = array;
array = new int[arrayLength];
for (int i = 0; i < aux.length; i++) {
array[i] = aux[i];
}
array[(arrayLength - 1)] = aux[(arrayLength - 2)];
}

int maxValue = array[0];
int minValue = array[0];
int i = 0;

while (i != arrayLength) {
if (array[i] > array[i + 1]) {
if (array[i] > maxValue) {
maxValue = array[i];
}
if (array[i + 1] < minValue) {
minValue = array[i + 1];
}
} else {
if (array[i + 1] > maxValue) {
maxValue = array[i + 1];
}
if (array[i] < minValue) {
minValue = array[i];
}
}
i += 2;
}

int secondMaxValue = minValue;
i = 0;
while (i != arrayLength) {
if ((array[i] > minValue) && (array[i] < maxValue)) {
minValue = array[i];
secondMaxValue = minValue;
}
i += 1;
}

return maxValue;
}
}

-

Here's a simple implementation which will return the max (first index in return array) and second distinct max (second index in return array) value as an array. If the list is size zero or there is no distinct max value, then Integer.MIN_VALUE is returned.

/**
* @param integer array
* @return an array comprising the highest distinct value (index 0) and second highest distinct
*         value (index 1), or Integer.MIN_VALUE if there is no value.
*/
public int[] findTwoHighestDistinctValues(int[] array)
{
int max = Integer.MIN_VALUE;
int secondMax = Integer.MIN_VALUE;

for (int value:array)
{
if (value > max)
{
secondMax = max;
max = value;
}
else if (value > secondMax && value < max)
{
secondMax = value;
}
}
return new int[] { max, secondMax };
}

-
+1: looks like the simplest solution. You may add a comment to explain that the second if also guarantees that max won't be equal to secondMax. – pgras Feb 25 '13 at 11:46
Some small enhancements: You could use a foreach loop, which would make it a bit more readable. The second branch condition could be secondMax < array[i] && array[i] < max which helps to see the effect. And I would add some JavaDoc, at least to document the return value. The rest is fine. – tb- Feb 27 '13 at 17:25
@tb - nice suggestions. Code updated accordingly. – Chris Knight Feb 27 '13 at 23:39

I'd be somewhat surprised if the code is correct, but even if it is, it has a lot of pointless stuff - comparing in pairs, aux array, minValue. A much better way is to find the max value, and the max value that's smaller than the first max. The naive way is to iterate through the array twice, but it can actually be done by iterating only once and updating both variables. One important question (to the initial problem) is what to do if the array does not contain 2 different values.

-
Thanks for your reply, i did this code running problably like you suggest with one "for" and comparing, if the number < vector, i update the second element and update also the max value...but if the first number is the higher valeu i can get the second max value... my code is running correct, i´ve tried to test with a array, ordened, unoderned and sorted – Diego Macario Feb 23 '13 at 0:14
@DiegoMacario are you saying that you have another version of the program, with a single "for"? If so, I'd like to see it. – aditsu Feb 23 '13 at 0:29
something like this... public void findElements(int[] array) { int maxValue = array[0]; int secondMaxValue = array[0]; for (int i = 0; i < array.length; i++) { if (array[i] > maxValue) { secondMaxValue = maxValue; maxValue = array[i]; } } } – Diego Macario Feb 23 '13 at 0:36
That's a very good start, except you're not handling one situation: what if array[i] is between the secondMaxValue and the maxValue? – aditsu Feb 23 '13 at 0:39
One example is: 2, 5, 3. Your code would find 5 and 2. – aditsu Feb 23 '13 at 0:44

Aside from corner case testing like no two distinct max values. If you assume an array size of at least two, and this might be more valid C# than java but....

int max1 = Math.Max(array[0], array[1]);
int max2 = Math.Min(array[0], array[1]);
if(max1 == max2) max2 = Int.MinValue;

//for loop 2...array length

int curr = array[idx];
if(curr > max1) {
max2 = max1; max1 = curr;
}
else if(curr > max2 && curr != max1) {
max2 = curr;
}

-
Something is weird. max1 and max2 are guaranteed to be the same at line 3. – Leonid Feb 23 '13 at 21:09
I would move the test max1 == max2 to the end. Like this would detect the case where the whole array does not contain two distinct values. – Olivier Jacot-Descombes Feb 24 '13 at 19:11

I don't want to sort the values.

Are you saying this because you don't realize how easy it is?

Sorting is the key insight to greatly simplify the code.

Implement, or override, the Java version of IComparible. The language automatically uses this to know how to sort. Search Java documentation and see if the Array class has a way to pass in a method that tells it how to sort. If not then make a custom class.

Then write methods that take advantage of the fact that it's dealing with a sorted array.

Consider the following as pseudo code, in C#

// a custom List of integers
public class MyList : List, IComparable {

// IComparible implementation
public int Compare (int thisValue, int otherValue) {
if(thisValue > otherValue) return 1;
if(thisValue < otherValue) return -1;
if(thisValue == otherValue) return 0;
}

public int getLargestValue() {
this.Sort();
return this[0];
}

public int getSecondLargestValue() {
int largest = this.getLargestValue();
int nextLargest;  //defaults to zero

foreach (int nextNum in this) {
nextLargest = nextNum;
if (nextLargest != largest) break;
}

return nextLargest;
}
}

// client code...

MyList integers = new MyList();
// fill it up with numbers here

int largest = integers.getLargestValue();
int nextLargest = integers.getSecondLargestValue();

-
Well, sorting is O(n*logn), so iterating over the entire array twice will generally be faster than sorting. – Leonid Feb 23 '13 at 21:11
Too bad we can't calculate big-O for the time to write, debug, extend, and simply comprehend code. The original code's problem is it's totally unnecessary size, complexity, and incomprehensibility. Once we bring some sanity to it then we can worry about performance. – radarbob Feb 24 '13 at 4:45
Well, if it was just an array of primitives, Arrays.sort() would do the trick, then just walk back from the end. – Eric P. Feb 24 '13 at 14:21
I don´t wanna use api Java, just code...like in c++ – Diego Macario Feb 26 '13 at 19:00