Related Tags

array

# How to find the k largest elements in an array

Ravi

## 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.

RELATED TAGS

array

CONTRIBUTOR

Ravi
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time 