Find the 2 distinct highest values in an array

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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();