Three greatest values in an array

Question

To find the three greatest elements in an array(length 100), is a combination of a for loop and an if statement(s) the most effective way, or is there a more efficient method?

Answer 1

For an array of length 100, and a max-3 items, you can even sort the array first and then take the top three elements - the performance difference is negligible.

For an array of greater size, a for-loop with an if comparing the 3 elements to the current one sounds fine.

If you have to find the top N elements of an M-sized array, then I think sorting would be most efficient.

Answer 2

Assuming the array is not sorted, you have to go through each element with a for loop (or something equivalent.)

There really isn't a more efficient way but to iterate for each element.

Answer 3

You should only have to traverse the list once, but yes, you will have to traverse it.(assuming it is not sorted).

Answer 4

I think you could do it with a single loop through the array, and I don't think you could do it faster. Something like:

int max1 = Integer.MIN_VALUE;
int max2 = Integer.MIN_VALUE;
int max3 = Integer.MIN_VALUE;  //assuming integer elements in the array

for (int i = 0; i < theArray.length; i++)
{
    if (theArray[i] > max1)
    {
        max3 = max2; max2 = max1; max1 = theArray[i];
    }
    else if (theArray[i] > max2)
    {
        max3 = max2; max2 = theArray[i];
    }
    else if (theArray[i] > max3)
    {
        max3 = theArray[i];
    }
}

If you want the top N elements in the array, you probably just want to sort it.

Answer 5

The best and most efficient way (in my own opinion) would be sorting the array first (preferably with Merge Sort) then get the top 3 values.

Answer 6

As this is java, you can always use a SortedSet (TreeSet for instance), that performs the sorting when elements are inserted, at a minimal cost (log(n)), and when you're done inserting, you can use descendingIterator() to retrieve the three greatest elements.

Answer 7

Your question is not very clear to me.

The most efficient way would be to maintain a max heap of size 3 and insert the array elements into the max heap one by one.

At the end the 3 elements in your max heap are the 3 largest elements in the original array.

In general the problem of finding max M elements in an array of size N is best solved by maintaining a max heap of size M.

Answer 8

A few people are posting saying that sorting is the way to go and then grab the top 3. However if there is a O(log N) insert into a sorted collection your will have to do it N times or to do a O(NlogN) sort (which by the way is a N^2 worst case scenario) you end up with NlogN efficiency as opposed to a simple O(N) of iterating through the array with a max1/max2/max3 like Riley posted above. Sorting or inserting into a sorted collection is the easiest but not the most efficient.