Try Finding the n largest values before reviewing the solution.

Review the solution with AP CS Tutor Brandon Horn.

Many solutions exist. The solutions below are based on Insertion Sort and Selection Sort.

Insertion Sort based findNLargest solution

public static int[] findNLargest(int[] nums, int n)
{
    int[] largest = new int[n];
    for(int i = 0; i < largest.length; i++)
        largest[i] = Integer.MIN_VALUE;

    for(int num : nums)
    {
        int i = -1;
        while(i + 1 < largest.length && num > largest[i + 1])
        {
            if(i + 1 > 0)
                largest[i] = largest[i + 1];

            i++;
        }

        if(i > -1)
            largest[i] = num;
    }

    return largest;
}

Basic logic

Array largest stores the largest n elements in nums, sorted in ascending order. Each element from nums is inserted into its correct position in largest. Elements that are no longer one of the n largest are dropped.

Details

Array largest is initialized with length n. Each value is set to Integer.MIN_VALUE. Finding the minimum or maximum discusses options for initial values for a min or max. Unlike when finding a single maximum, the values in largest cannot all be initialized to nums[0].

Throughout the method, array largest stores the n largest known values, sorted in ascending order (and Integer.MIN_VALUE until at least n elements of nums have been visited).

The outer loop visits each element in nums exactly once. Unlike in Insertion Sort, the loop does not skip the first element. The order in which the elements in nums are visited doesn’t matter.

The loop body is a variant of the Insertion Sort inner loop. Elements from nums are inserted into their correct positions in largest, with elements from largest shifting to the left to make room. Only largest is modified. The elements in nums are never changed.

The variable i stores the position in largest at which num (an element from nums) should be inserted, or -1 if num should not be inserted into largest.

Although the while loop moves from left to right in largest, it uses the same logic as Insertion Sort’s while loop. The loop runs while num belongs at an index in largest greater than i.

largest.length might be less than nums.length. The conditional if(i + 1 > 0) determines if an element of largest has a place to go. An element of largest that does not have a place to go, because it is no longer one of the n largest, is left in place (and will be overwritten).

Unlike in Insertion Sort, not every element of nums is inserted into largest. The conditional if(i > -1) determines if num (an element of nums) should be inserted, because it is (at least for now) one of the n largest.

The precondition guarantees that all occurrences of Integer.MIN_VALUE will be shifted out of largest, unless nums contains Integer.MIN_VALUE.

Selection Sort based findNLargest solution

public static int[] findNLargest(int[] nums, int n)
{
    int[] numsCopy = nums.clone();

    for(int i = 0; i < n; i++)
    {
        int maxIndex = i;

        for(int j = i + 1; j < numsCopy.length; j++)
            if(numsCopy[j] > numsCopy[maxIndex])
                maxIndex = j;

        int temp = numsCopy[maxIndex];
        numsCopy[maxIndex] = numsCopy[i];
        numsCopy[i] = temp;
    }

    int[] largest = new int[n];
    int ncIndex = 0;
    for(int largestIndex = largest.length - 1; largestIndex >= 0; largestIndex--)
    {
        largest[largestIndex] = numsCopy[ncIndex];
        ncIndex++;
    }

    return largest;
}

Basic logic

The Selection Sort algorithm is run for n iterations, instead of through the entire array. The algorithm finds the max instead of the min. Once the n largest elements are at the beginning of the array, they are copied into a new array in reverse order.

Details

Unlike the Insertion Sort based solution, this Selection Sort based solution modifies the array. The method requires that the array remain unchanged, so numsCopy is set to a copy of nums. The rest of the code works with numsCopy and ignores nums.

The first for loop runs n times. Unlike Selection Sort, the loop does not skip the last element.

The loop body is identical to Selection Sort, except it finds the max instead of the min. As in Selection Sort, each max is swapped with the first element in the unchecked part of the array.

After the first for loop, the n largest elements are at the beginning of numsCopy, sorted in descending order. The remaining elements in numsCopy are unchecked.

The last for loop copies the n largest elements from numsCopy into largest. The elements are copied into largest backwards, so they are in ascending order.

Comments

Comment on Finding the n largest values in an array