Finding all indices of largest value in an array

Question

I have the following code that gives me the indices of an array's largest value:

public static void main(String[] args) {

    float[] elementList = new float[7];
    elementList[0] = 8F;
    elementList[1] = 5F;
    elementList[2] = 4F;
    elementList[3] = 3F;
    elementList[4] = 0F;
    elementList[5] = 8F;
    elementList[6] = 6F;
    // findLargestNumberLocations(elementList);
    largestNumbers(elementList);
}

private static void largestNumbers(float[] numbers) {

    float largeNumber = numbers[0];
    for (int i = 0; i < numbers.length; i++) {
        if (numbers[i] > largeNumber) {
            largeNumber = numbers[i];
        }
    }
    for (int j = 0; j < numbers.length; j++) {
        if(largeNumber == numbers[j]){
            System.out.println("largest number index "+j);
        }
    }
}

Is there any optimized way of doing this?

Answer 1

In this case, your performance will not be terrible, but, for really large arrays you may run in to problems.

Also, there is a bug in your code... what if the input array is empty? Then you will get an ArrayIndexOutOfBoundsException on:

float largeNumber = numbers[0];

There is always more than one way to do things, but, I want to post an answer here because one possible solution (which may or may not be faster than your solution depending on data size) has a really close relationship to another CodeReview question posted recently. When I answered that question I could only think of artifical examples of when it was 'right' to use pre/post-increments. This is a good example of when....

See this answer here: Is it bad practice to increment more than one variable in a for loop declaration?

So, here is a good example of how and when a count and an index are related in a for loop and the way they can be incremented. I have some notes at the end:

private static int[] findLargeNumberIndices(float[] numbers) {

    // create an array of at least 8 members.
    // We may need to make this bigger during processing in case
    // there's more than 8 values with the same large value
    int[] indices = new int[Math.max(numbers.length / 16 , 8)];
    // how many large values do we have?
    int count = 0;
    // what is the largest value we have?
    float largeNumber = Float.NEGATIVE_INFINITY;
    for (int i = 0; i < numbers.length; i++) {
        if (numbers[i] > largeNumber) {
            // we have a new large number value... reset our history....
            largeNumber = numbers[i];
            // setting count to zero is enough to 'clear' our previous references.
            count = 0;
            // we know there's space for at least index 0. No need to check.
            // note how we post-increment - this is a 'pattern'.
            indices[count++] = i;
        } else if (numbers[i] == largeNumber) {
            // we have another large value.
            if (count == indices.length) {
                // need to make more space for indices... increase array by 25%
                // count >>> 2 is the same as count / 4 ....
                indices = Arrays.copyOf(indices, count + (count >>> 2));
            }
            // again, use the post-increment
            indices[count++] = i;
        }
    }
    // return the number of values that are valid only.
    return Arrays.copyOf(indices, count);
}

Notes about this code:

1. The presentation (System.out.println(...)) is now outside the method.
2. It allocates a 'small' array to store the indexes. This array will grow if needed.
3. I picked 'good enough` initial size for the array.... but some playing with the numbers may help performance.
4. There is no real reason to believe that this code is faster than the two loops - creating the array may be more expensive than the second loops.
5. note how the i index is incemented in the for-loop, but the `count` is post-incremented each time it is used in the array.

Answer 2

Your code doesn't just find the largest number's index. It finds the largest number, then searches again for any indices that match that value.

Here's a method that uses less searching (pseudocode):

largestValue = numbers[0];
vector largestIndices; // Will store all indices of largestValue as you search
largestIndices.add(0); // In case numbers[0] = the true largest value

for (i = 1; i < numbers.size(); i++) { // don't need to compare index 0
    if (numbers[i] > largestValue) {
        largestValue = numbers[i]; // Update largestValue
        largestIndices.clear();    // Get rid of indices of smaller values
        largestIndices.add(i);     // Add this index
    }
    else if (numbers[i] == largestValue) {
        largestIndices.add(i);     // Add this index
    }
}

for (j = 0; j < largestIndices.size(); j++) {
    // no searching necessary!
    print(largestIndices[j]);
}

This probably uses more data accesses, but saves searching time (important for huge arrays).

Answer 3

Is the new line after a function starts intended?

---

private static void largestNumbers(float[] numbers) {

This function could have a better name, functions should have a verb as name, not an adjective.

private static void printLargestNumbersIndex(float[] numbers)

This is more verbose, but you immediately know what the function does.

---

float largeNumber = numbers[0];

Very minor, but I'd call it largestNumber.

---

for (int i = 0; i < numbers.length; i++) {
    if (numbers[i] > largeNumber) {
        largeNumber = numbers[i];
    }
}

A foreach loop would be more appropriate for this use case.

for (float number : numbers) {
    if (number > largestNumber) {
        largestNumber = number;
    }
}

Generally always try to use foreach loops instead of for loops unless you need to know the index of the element (which would be the case in the second loop).

---

for (int j = 0; j < numbers.length; j++) {

For myself I try to avoid one-letter variables as hard as possible (only exception being coordinates, x y z), and this opinion is for sure controversial and non-standard, but I think this loop would gain a lot of readability by simply using index as variable.

for (int index = 0; index < numbers.length; index++) {

---

if(largeNumber == numbers[j]){

Always keep in mind that comparing floating point numbers with == can be problematic.

---

System.out.println("largest number index "+j);

Ideally, from a code structure and reuse point of view, your function would return an int[] or Collection<Integer> with all found indexes. That would make it easily reusable.

---

float[] elementList = new float[7];
elementList[0] = 8F;
elementList[1] = 5F;
elementList[2] = 4F;
elementList[3] = 3F;
elementList[4] = 0F;
elementList[5] = 8F;
elementList[6] = 6F;

You can initialize arrays directly with values.

float[] elementList = new float[] {8f, 5f, 4f, 3f, 0f, 8f, 6f};

Also, elementList is not a great name for this.

Answer 4

Your code is correct, except that you get an ArrayOutOfBoundsException for an empty input list. You'll have to decide what the desired behaviour should be for an empty input, but ArrayOutOfBoundsException isn't quite appropriate. IllegalArgumentException maybe, if you document the requirement that numbers be non-empty. Personally, I think that an empty input should produce empty output.

Mixing logic and output is bad practice, as it ensures that your code will not be reusable. You should return an array instead of printing the results.

I suggest renaming your function to include "max" in the name instead of "largest", as almost all APIs prefer "max", including java.lang.Math.max().

The primary performance concern would be that you iterate through the array twice. That may or may not be acceptable, depending on the size of the input you expect. Either way, the performance will be O(n), though you'll notice a significant difference for large n.

@trojansdestroy suggests building the result set as as list in one pass. @rolfl suggests building the result set using arrays in one pass, which accomplishes the same thing the hard way to avoid the overhead of creating an ArrayList and its associated boxing-unboxing conversion.

In contrast to those two approaches, I prefer to make two passes. The first pass finds the largest number and the size of the result set. The second pass fills in the result set.

/**
 * Finds the locations of the largest numbers.  Any Float.NaN
 * elements in the input are ignored.
 *
 * @return An empty array if numbers is empty or consists solely
 *         of Float.NaN; null if numbers is null; an array of
 *         indexes otherwise.
 */
public static int[] maxIndexes(float[] numbers) {
    if (null == numbers) return null;

    int maxIndex = 0, maxCount = 0;

    // In case the array starts with Float.NaN
    while (maxIndex < numbers.length - 1 && Float.isNaN(numbers[maxIndex])) {
        maxIndex++;
    }

    // First pass: identify the max value and the number of times it occurs
    for (int i = maxIndex; i < numbers.length; i++) {
        if (numbers[i] > numbers[maxIndex]) {
            maxIndex = i;
            maxCount = 1;
        } else if (numbers[i] == numbers[maxIndex]) {
            maxCount++;
        }
    }

    // Second pass: Write the result
    int[] ret = new int[maxCount];
    for (int i = numbers.length - 1; i >= maxIndex; i--) {
        if (numbers[i] == numbers[maxIndex]) {
            ret[--maxCount] = i;
        }
    }
    return ret;
}

There's a slight optimization on the second pass, so that it might not have to loop through the entire array.

Which strategy will work best in practice? Most processes that generate floating-point numbers won't produce many numbers that are exactly equal to each other, so I would guess that @rolfl has the most practical code.

Your test case would be…

public static void main(String[] args) {
    float[] numbers = { 8f, 5f, 4f, 3f, 0f, 8f, 6f };
    int[] max = maxIndexes(numbers);
    System.out.println(java.util.Arrays.toString(max));
}

Note the simplified array initializer. You could even omit the f suffix on the float literals and let the compiler figure it out.