215. Kth Largest Element in an Array – Leetcode Solutions

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

import heapq

class Solution:
    def findKthLargest(self, nums: list[int], k: int) -> int:
        # Create a min-heap of size k with the first k elements of nums
        min_heap = nums[:k]
        heapq.heapify(min_heap)  # Turn the list into a heap
        
        # Iterate through the remaining elements in nums
        for num in nums[k:]:
            # If the current number is larger than the smallest element in the heap
            if num > min_heap[0]:
                # Replace the smallest element with the current number
                heapq.heapreplace(min_heap, num)
        
        # The root of the heap (min_heap[0]) is the kth largest element
        return min_heap[0]

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    // A helper function to maintain the min-heap property
    const heapify = (heap, i, heapSize) => {
        let smallest = i; 
        let left = 2 * i + 1;
        let right = 2 * i + 2;

        // If the left child is smaller than the current smallest
        if (left < heapSize && heap[left] < heap[smallest]) {
            smallest = left;
        }

        // If the right child is smaller than the current smallest
        if (right < heapSize && heap[right] < heap[smallest]) {
            smallest = right;
        }

        // If the smallest element is not the current element
        if (smallest !== i) {
            // Swap elements
            [heap[i], heap[smallest]] = [heap[smallest], heap[i]];

            // Recursively heapify the affected sub-tree
            heapify(heap, smallest, heapSize);
        }
    };

    // Build a min-heap of size k with the first k elements
    const minHeap = nums.slice(0, k);
    
    // Create the initial heap
    for (let i = Math.floor(k / 2) - 1; i >= 0; i--) {
        heapify(minHeap, i, k);
    }

    // Iterate through the remaining elements in nums
    for (let i = k; i < nums.length; i++) {
        if (nums[i] > minHeap[0]) {
            // Replace the root of the heap (smallest element)
            minHeap[0] = nums[i];
            
            // Re-heapify to maintain the min-heap property
            heapify(minHeap, 0, k);
        }
    }

    // The root of the heap is the kth largest element
    return minHeap[0];
};

import java.util.PriorityQueue;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // Create a min-heap (priority queue) to store the top k largest elements
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);

        // Iterate over each element in the nums array
        for (int num : nums) {
            // Add the current number to the heap
            minHeap.offer(num);
            
            // If the size of the heap exceeds k, remove the smallest element
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        
        // The root of the heap is the kth largest element
        return minHeap.peek();
    }
}

using System;
using System.Collections.Generic;

public class Solution {
    public int FindKthLargest(int[] nums, int k) {
        // Create a priority queue (min-heap) to store the top k largest elements
        PriorityQueue<int, int> minHeap = new PriorityQueue<int, int>();

        // Iterate over each element in the nums array
        foreach (int num in nums) {
            // Add the current number to the heap
            minHeap.Enqueue(num, num);
            
            // If the size of the heap exceeds k, remove the smallest element
            if (minHeap.Count > k) {
                minHeap.Dequeue();
            }
        }
        
        // The root of the heap is the kth largest element
        return minHeap.Peek();
    }
}