Finding Top N Items in Array

Learn to find the top N items in a given array in Java. Note that we should be very clear about the meaning of top N items. The suggested solution may need minor changes based on our interpretation and requirement.

For example, in this tutorial, top N items mean the top N largest items in the array.

1. Find Top N Items using Queues

The Queue data structure maintains the ordering of the elements based on their priority. The good thing is that we can decide the priority by giving a custom Comparator.

In the given examples, we want to find the top 3 largest values in an array of Integers.

1.1. PriorityQueue

PriorityQueue is an unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, and the head of this queue is the least element.

So if we add the integers in this queue and keep polling the items to keep its size limited to 3, we will have the 3 largest integer values in the queue when the loop ends.

Integer[] items = {0, 10, 30, 2, 7, 5, 90, 76, 100, 45, 55};

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(3);

for (Integer i : items) {
    priorityQueue.add(i);
    if (priorityQueue.size() > 3)
        priorityQueue.poll();
}

System.out.println("Items are : " + priorityQueue); //[76, 100, 90]

1.2. MinMaxPriorityQueue

MinMaxPriorityQueue class is part of Guava collections. It is a double-ended priority queue that provides constant-time access to both its least element and its greatest element, as determined by the queue’s specified comparator or natural ordering.

When we compare the solutions with MinMaxPriorityQueue and PriorityQueue, we do not need to perform the extra polling operation and check the queue size with each iteration.

Include Guava’s latest version from the Maven repository.

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>${guava-version}</version>
</dependency>
Integer[] items = {0, 10, 30, 2, 7, 5, 90, 76, 100, 45, 55};
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(3);

MinMaxPriorityQueue<Integer> minMaxQueue =
        MinMaxPriorityQueue.orderedBy(Collections.reverseOrder())
            .maximumSize(3)
            .create();

for (Integer i : items) {
    minMaxQueue.add(i);
}

System.out.println("Items are : " + minMaxQueue); [100, 90, 76]

2. Using Stream API

Java Stream API is a great collection of super useful methods that can perform very complex tasks with simple method invocations.

For finding top N items in Stream, we need to sort the items in the stream and collect the three items from such stream.

Integer[] items = {0, 10, 30, 2, 7, 5, 90, 76, 100, 45, 55};

List<Integer> top3ItemsInList = Arrays.stream(items)
                .sorted(Collections.reverseOrder())
                .limit(3)
                .collect(Collectors.toList());

System.out.println("Items are : " + top3ItemsInList); //[100, 90, 76]

3. Arrays.copyOfRange()

The copyOfRange() API copies the specified range of a given array into a new array. So if we can sort an array, we can easily pick its first 3 item indices because they will definitely be the top 3 items.

Integer[] items = {0, 10, 30, 2, 7, 5, 90, 76, 100, 45, 55};

Arrays.sort(items, Collections.reverseOrder());

Integer[] topThreeItems = Arrays.copyOfRange(items, 0, 3);
System.out.println("Items are : " + Arrays.toString(topThreeItems)); //[100, 90, 76]

4. Conclusion

This tutorial taught us to find the top N items from an array. The top N items can be the N largest items or the N smallest items. It depends on the usecase.

We learned to find the items using the Queues, Streams and copy array range functionality. We can build more similar approaches as per our needs.

Note that only PriorityQueue does not sort the array while all other solutions work on the sorted array, or they internally maintain a sorting. So if you wish to preserve the ordering of top N items unchanged as it was in the original array then please use PriorityQueue.

Happy Learning !!

Sourcecode on Github

Was this post helpful?

Join 7000+ Awesome Developers

Get the latest updates from industry, awesome resources, blog updates and much more.

* We do not spam !!

Leave a Comment

HowToDoInJava

A blog about Java and related technologies, the best practices, algorithms, and interview questions.