Kth Largest Element in an Array - Java Solution

1. Introduction

This blog post explores a common algorithmic problem known as the "Kth Largest Element in an Array". The challenge is to find the kth largest element in a given unsorted array. It's a problem often encountered in scenarios involving sorting, ordering, and priority queues.

Problem

Given an integer array nums and an integer k, the task is to return the kth largest element in the array. It's important to note that the requirement is to find the kth largest element in the sorted order, not the kth distinct element. The solution should ideally avoid a complete sort of the array.

Examples:

1. Input: nums = [3,2,1,5,6,4], k = 2

Output: 5

2. Input: nums = [3,2,3,1,2,4,5,5,6], k = 4

Output: 4

2. Solution Steps

1. Utilize a priority queue (min heap) to keep track of the k largest elements.

2. Iterate through the array, adding each element to the heap.

3. Once the size of the heap exceeds k, remove the smallest element from the heap.

4. After processing all elements, the root of the heap will be the kth largest element.

5. Return the element at the root of the heap.

3. Code Program

import java.util.PriorityQueue;

public class KthLargestElement {
    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        System.out.println(findKthLargest(nums, k)); // Test the function
    }

    // Function to find the kth largest element in an array
    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int num : nums) {
            heap.add(num);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        return heap.peek();
    }
}

Output:

5

Explanation:

1. findKthLargest: This function finds the kth largest element in the array nums.

2. It uses a min heap (priority queue) to efficiently track the k largest elements in the array.

3. As the function iterates through the array, it adds each element to the heap. If the heap size exceeds k, it removes the smallest element, ensuring that only the k largest elements remain.

4. After processing the entire array, the root of the heap contains the kth largest element.

5. This approach avoids the need to sort the entire array, which can be more efficient, especially for large arrays. It leverages the properties of a min heap to maintain a running list of the k largest elements with each iteration.