Kth Largest Element in an Array medium

Problem Statement

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

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

Example 2:

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

Steps and Explanation

This problem can be efficiently solved using a min-heap data structure. Here's the breakdown:

1. Create a Min-Heap: We'll use a min-heap to store the k largest elements encountered so far. A min-heap ensures that the smallest element is always at the root.

2. Iterate Through the Array: We iterate through the input array nums.

3. Compare and Add/Replace: For each element:

   • If the size of the min-heap is less than k, we add the element to the heap.
   • If the size of the min-heap is equal to k and the current element is greater than the root (smallest element) of the heap, we replace the root with the current element and then heapify (re-arrange the heap to maintain the min-heap property). This ensures that the heap always contains the k largest elements seen so far.

4. Return the Root: After iterating through the entire array, the root of the min-heap will be the kth largest element.

Code (C#)

using System;
using System.Collections.Generic;

public class Solution {
    public int FindKthLargest(int[] nums, int k) {
        // Create a min-heap using PriorityQueue (default min-heap in C#)
        PriorityQueue<int, int> minHeap = new PriorityQueue<int, int>();

        // Iterate through the array
        foreach (int num in nums) {
            // Add to heap if size < k
            if (minHeap.Count < k) {
                minHeap.Enqueue(num, num); // Use num as priority for min-heap
            } else {
                // If heap is full and current element > root, replace root
                if (num > minHeap.Peek()) {
                    minHeap.Dequeue();
                    minHeap.Enqueue(num, num);
                }
            }
        }

        // Return the root (kth largest element)
        return minHeap.Peek();
    }
}

Complexity Analysis

• Time Complexity: O(N log k), where N is the length of the input array. Adding and removing from the heap takes O(log k) time in each iteration.
• Space Complexity: O(k), as the min-heap stores at most k elements.

This solution is efficient because it avoids fully sorting the entire array. It only maintains a heap of size k, making it suitable even for large input arrays and large values of k. Using a PriorityQueue simplifies the heap management in C#. If you were working in a language without a built-in priority queue, you would need to implement a min-heap yourself, which would add to the complexity but not change the overall time complexity significantly.