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 AI Mock Interviews
Coding Interview
Coding PatternsFree Interview
Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.
System Design
YouTubeFree Interview
Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

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