Java - K Largest Elements in an Array
Problem Statement
Given an array arr[] of N integers and an integer K, find the K largest elements in the array in descending order.
Example 1:
Input:
arr = {3, 2, 1, 5, 6, 4}, K = 2
Output: [6, 5]
Example 2:
Input:
arr = {12, 5, 787, 1, 23}, K = 3
Output: [787, 23, 12]
Approach 1: Sorting (O(N log N))
Sort the array in descending order.
Pick the first K elements.
Code Implementation
import java.util.Arrays;
public class KLargestElementsSorting {
public static int[] kLargest(int[] arr, int K) {
Arrays.sort(arr); // Sort in ascending order
int[] result = new int[K];
int n = arr.length;
// Pick the last K elements (largest elements)
for (int i = 0; i < K; i++) {
result[i] = arr[n - 1 - i];
}
return result;
}
public static void main(String[] args) {
int[] arr = {3, 2, 1, 5, 6, 4};
int K = 2;
System.out.println(Arrays.toString(kLargest(arr, K)));
// Output: [6, 5]
}
}
Complexity Analysis
Approach Time Complexity Space Complexity
Sorting O(N log N) O(1) (in-place sort)
Approach 2: Min-Heap (O(N log K)) - Efficient for Large N
Use a Min-Heap (PriorityQueue in Java) of size K.
Traverse the array:
Insert elements into the Min-Heap.
If the heap size exceeds K, remove the smallest element.
At the end, the heap contains the K largest elements.
Extract elements from the heap and sort them in descending order.
Code Implementation
import java.util.*;
public class KLargestElementsHeap {
public static List<Integer> kLargest(int[] arr, int K) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // Min-Heap
// Step 1: Maintain min-heap of size K
for (int num : arr) {
minHeap.add(num);
if (minHeap.size() > K) {
minHeap.poll(); // Remove the smallest element
}
}
// Step 2: Extract elements and sort in descending order
List<Integer> result = new ArrayList<>(minHeap);
result.sort(Collections.reverseOrder());
return result;
}
public static void main(String[] args) {
int[] arr = {3, 2, 1, 5, 6, 4};
int K = 2;
System.out.println(kLargest(arr, K));
// Output: [6, 5]
}
}
Complexity Analysis
Step Time Complexity
Building the heap O(K log K)
Processing remaining (N - K) elements O((N-K) log K)
Sorting result list O(K log K)
Total Complexity O(N log K)
✅ Best for large N when K is small.
Approach 3: QuickSelect (O(N) Average, O(N²) Worst)
This is based on the QuickSort partition method.
Use QuickSelect (similar to QuickSort).
Select a pivot and partition the array.
If the pivot position is N-K, return the last K elements.
If N-K is on the left, recurse on the left side.
Otherwise, recurse on the right side.
Code Implementation
import java.util.Arrays;
public class KLargestElementsQuickSelect {
public static int[] kLargest(int[] arr, int K) {
int N = arr.length;
quickSelect(arr, 0, N - 1, N - K); // Find K largest elements
int[] result = Arrays.copyOfRange(arr, N - K, N); // Extract K largest
Arrays.sort(result); // Sort in ascending order
return result;
}
private static void quickSelect(int[] arr, int left, int right, int K) {
if (left < right) {
int pivotIndex = partition(arr, left, right);
if (pivotIndex == K) return;
else if (pivotIndex < K) quickSelect(arr, pivotIndex + 1, right, K);
else quickSelect(arr, left, pivotIndex - 1, K);
}
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[right], i = left;
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
swap(arr, i, j);
i++;
}
}
swap(arr, i, right);
return i;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {3, 2, 1, 5, 6, 4};
int K = 2;
System.out.println(Arrays.toString(kLargest(arr, K)));
// Output: [5, 6]
}
}
