Problem #215: Kth Largest Element in an Array

Intuition & Strategy Breakdown

Use a min-heap of size K (or Quickselect algorithm). Push elements into heap; if heap size > K pop min, leaving Kth largest at root.

Python Solution

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        target = len(nums) - k
        
        def partition(left, right):
            pivot = nums[right]
            i = left
            for j in range(left, right):
                if nums[j] <= pivot:
                    nums[i], nums[j] = nums[j], nums[i]
                    i += 1
            nums[i], nums[right] = nums[right], nums[i]
            return i
            
        left, right = 0, len(nums) - 1
        while left <= right:
            pivot_idx = partition(left, right)
            if pivot_idx == target:
                return nums[pivot_idx]
            elif pivot_idx < target:
                left = pivot_idx + 1
            else:
                right = pivot_idx - 1

Java Solution

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int target = nums.length - k;
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int pivotIdx = partition(nums, left, right);
            if (pivotIdx == target) {
                return nums[pivotIdx];
            } else if (pivotIdx < target) {
                left = pivotIdx + 1;
            } else {
                right = pivotIdx - 1;
            }
        }
        return -1;
    }

    private int partition(int[] nums, int left, int right) {
        int pivot = nums[right];
        int i = left;
        for (int j = left; j < right; j++) {
            if (nums[j] <= pivot) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                i++;
            }
        }
        int temp = nums[i];
        nums[i] = nums[right];
        nums[right] = temp;
        return i;
    }
}