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?

• 200_success: What would you like the behaviour to be for an empty input? What if any of the numbers is Float.NaN?
• MaheshVarma: Edited the OP, Please let me know if there is any mistake. @200_success
• 200_success: I've rolled back your edit. Please don't alter the question, as it invalidates all the reviews. I just wanted to seek clarification. Your wish appears to be: 1) NullPointerException if numbers is null, 2) No output if numbers is empty, 3) Ignore all Float.NaN.
• MaheshVarma: Yes, That is how I did

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.

• Mathieu Guindon: Serindipitously upvoted :)
• MaheshVarma: Nice explanation... can we directly tell count/4 is same as count >>> 2. Or does it come with experience? I never used this shift operator but I have an idea on this. From now on I will try to use this operator. But how to decide the result of x >>> 3 or x <<< 5 or x << 8. do we need to calculate binary digits and decide, oh! count >>> 4 is equal to count/4 ? Please give some idea on these shift operators in real time? @rolfl
• rolfl: @MaheshVarma - you can divide by any power-of-2 by using bit-shifts. 0, 1, 2, 3, ... bitshifts respectively mean divide by 1, 2, 4, 8, .... (or multiply by if it is a left-shift). The easiest explanation for it is to think in decimal: 12345 integer-divided by 100 is 123.... we 'shifted' 2 digits (2nd power of 10). Similarly, 12345 multiplied by 100 is 1234500 - we left-shifted twice. When you multiply/divide by powers-of-two, the shift operator is sometimes more convenient.
• MaheshVarma: What could be the real time uses of these shift operators?
• rolfl: @MaheshVarma - in this case they are essentially useless, but, in certain situations they are very, very useful... here's a good starting point: stackoverflow.com/questions/520625/…

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.

• MaheshVarma: Thank you for clear explanation, does it give performance? @Bobby
• Bobby: @MaheshVarma: You mean that initializer thing? Too minor to notice if at all, but it increases readability.
• MaheshVarma: I mean can we do it both finding the largest number and printing out it's indices in single for loop? @Bobby
• Max: upvote but I oppose the idea of using idx as the variable name. i is industry standard and is perfectly fine. If you wish to move away from using industry standard I'd suggest using index as a more declarative alternative to idx.
• Max: @Bobby It's true that in a bigger scope (i.e., lots of nesting etc) a more descriptive variable name as index should be used, I agree with you on that. That is not the case here though.

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.

• MaheshVarma: Please review the edited version.
• 200_success: The code in questions should not be edited in any significant way after the question has been posed, as that would invalidate the reviews.