Kth Largest Element in an Array

Description

Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Can you solve it without sorting?

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

Constraints:

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

Primary Approach: Min-Heap ($O(N\log k)$ Time, $O(k)$ Space)

Intuition

To find the $k$-th largest element in an array, maintain a Min-Heap (PriorityQueue) of size $k$:

1. Iterate through all elements in nums and push each element into the min-heap.
2. If minHeap.size() exceeds $k$, evict the top element (minHeap.poll()). The top is always the smallest among the elements currently in the heap.
3. After processing the entire array, the top of the min-heap (minHeap.peek()) holds the $k$-th largest element.

import java.util.PriorityQueue;
 
class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
 
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
 
        return minHeap.peek();
    }
}
 

Complexity

• Time Complexity: $O(N\log k)$ — We iterate through $N$ elements and perform heap insertion/eviction operations taking $O(\log k)$ time each.
• Space Complexity: $O(k)$ — The min-heap stores at most $k$ elements simultaneously.

---

Optimal Average Time Approach: Quickselect Algorithm ($O(N)$ Avg Time, $O(1)$ Space)

Intuition

Quickselect is a Divide and Conquer algorithm derived from QuickSort. Finding the $k$-th largest element in nums is equivalent to finding the element at index target = nums.length - k in a fully sorted array:

1. Select a pivot element at random to avoid worst-case $O(N^2)$ behavior on pre-sorted arrays.
2. Partition the array into elements smaller than the pivot on the left and larger on the right.
3. If the pivot’s final index matches target, return nums[pivot].
4. If the pivot index is greater than target, recurse only on the left subarray; otherwise, recurse on the right subarray.

import java.util.Random;
 
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int target = nums.length - k;
        return quickSelect(nums, 0, nums.length - 1, target);
    }
 
    private int quickSelect(int[] nums, int left, int right, int target) {
        if (left == right) return nums[left];
 
        // Pick a random pivot index to ensure O(N) average time
        int pivotIndex = left + new Random().nextInt(right - left + 1);
        pivotIndex = partition(nums, left, right, pivotIndex);
 
        if (pivotIndex == target) {
            return nums[pivotIndex];
        } else if (pivotIndex < target) {
            return quickSelect(nums, pivotIndex + 1, right, target);
        } else {
            return quickSelect(nums, left, pivotIndex - 1, target);
        }
    }
 
    private int partition(int[] nums, int left, int right, int pivotIndex) {
        int pivotValue = nums[pivotIndex];
        // Move pivot to the end
        swap(nums, pivotIndex, right);
        int storeIndex = left;
 
        for (int i = left; i < right; i++) {
            if (nums[i] < pivotValue) {
                swap(nums, storeIndex, i);
                storeIndex++;
            }
        }
        // Move pivot to its final place
        swap(nums, storeIndex, right);
        return storeIndex;
    }
 
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
 

Complexity

• Time Complexity:
  • Average: $O(N)$ — $N+\frac{N}{2}+\frac{N}{4}+\cdots \approx 2N$ total operations.
  • Worst Case: $O(N^2)$ — If bad pivots are repeatedly chosen (mitigated using random pivot selection).
• Space Complexity: $O(1)$ auxiliary space ($O(\log N)$ stack depth for recursive calls).

---

Key Interview Discussion Points

• Min-Heap vs. Quickselect:
  • Min-Heap ($O(N\log k)$): Simple to implement, deterministic, and ideal for data streams where array elements arrive continuously.
  • Quickselect ($O(N)$ Average): Better theoretical average time complexity and operates in-place ($O(1)$ extra space).
• Handling Duplicate Elements: Standard Quickselect can suffer performance degradation when arrays contain many duplicate values. Modern LeetCode test cases enforce random pivot selection or 3-way partitioning to prevent Time Limit Exceeded (TLE).

---

Easy Memory Rule

“Finding $k$-th LARGEST in static array? Use MIN-HEAP of size $k$ for clean code, or QUICKSELECT to target index N - k for $O(N)$ average time!”