How to find the k largest elements in an array

Problem statement

Given an array of integers with elements in random order, find the k largest elements in the array.

Note: There are no duplicate elements in the array.

Example 1

  • Input: arr=[8, 4, 1, 9, 2], k=3
  • Output: [4, 8, 9]

Example 2

  • Input: arr=[8, 4, 1, 9, 2], k=8
  • Output: -1

As the value of k is greater than the length of the array, we return -1.

Solution

The solution to the problem is to use sorting. Once the array is sorted in descending order, the first k elements in the array are the k largest elements in the array.

The steps of the algorithm are as follows:

  1. Sort the array in descending order. We can use quick sort or merge sort.
  2. Return the first k elements in the sorted array.
  • Time complexity: O(n log(n))
  • Space complexity: O(n)

Code

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
class Main{
    public static void kLargest(int[] arr, int k){
        List<Integer> integerList = Arrays.stream(arr).boxed().sorted(Collections.reverseOrder()).collect(Collectors.toList());
        for(int i=0;i<k;i++)
            System.out.print(integerList.get(i) + " ");
    }
    public static void main(String[] args) {
        int[] arr = new int[]{8, 4, 1, 9, 2};
        int k = 3;
        kLargest(arr, k);
    }
}

Explanation

  • Lines 1–4: We import the relevant classes.
  • Lines 8–12: We define a function called kLargest() that takes an integer array arr and k. First we convert the integer array to a list using the streams API. Then the stream is sorted in descending order. Lastly, we print the first k elements of the sorted list.
  • Line 15: We define an integer array, arr.
  • Line 16: We define k.
  • Line 17: We invoke the kLargest() function, arr and k.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)