Java – find the highest n numbers in an infinite list

I was asked this question in a recent Java interview

The following is what I have done. If someone can provide a more efficient or elegant solution, I will be grateful, because I believe it can also be solved by using PriorityQueue:

public TreeSet<Integer> findTopNNumbersInLargeList(final List<Integer> largeNumbersList,final int highestValCount) {

    TreeSet<Integer> highestNNumbers = new TreeSet<Integer>();

    for (int number : largeNumbersList) {
        if (highestNNumbers.size() < highestValCount) {
            highestNNumbers.add(number);
        } else {
            for (int i : highestNNumbers) {
                if (i < number) {
                    highestNNumbers.remove(i);
                    highestNNumbers.add(number);
                    break;
                }
            }
        }
    }
    return highestNNumbers;
}

Solution

You don't need to nest loops, just keep inserting and delete the smallest number when the collection is too large:

public Set<Integer> findTopNNumbersInLargeList(final List<Integer> largeNumbersList,final int highestValCount) {

  TreeSet<Integer> highestNNumbers = new TreeSet<Integer>();

  for (int number : largeNumbersList) {
    highestNNumbers.add(number);
    if (highestNNumbers.size() > highestValCount) {
      highestNNumbers.pollFirst();
    }
  }
  return highestNNumbers;
}

The same code should also be used with PriorityQueue In any case, the runtime should be o (n log highestvalcount)

PS: as pointed out in another answer, you can further optimize (at the expense of readability) by tracking the minimum number to avoid unnecessary insertion