215. Kth Largest Element in an Array

# Question

Given an unsorted integer array nums and an integer k, return the $k^{th}$ largest element in the array.

Note: It is the $k^{th}$ largest element in sorted order, not the $k^{th}$ distinct element.

# Solution

# Pattern

Quickselect (Hoare's / Lomuto Partitioning) A selection algorithm related to Quicksort. Instead of sorting both sides of a partition, we only recurse into the side containing our target index.

# How to Identify

• Find the $k^{th}$ smallest/largest element.
• Requirement for $O(n)$ average time complexity.
• Constraints suggest that sorting ($O(n \log n)$) is too slow or unnecessary.

# Description

Step-by-step explanation:

1. Target Index: In a sorted array of size $n$, the $k^{th}$ largest element is at index target = n - k.
2. Partitioning: Pick a pivot (randomly to avoid worst-case). Move all elements smaller than the pivot to its left and larger to its right.
3. Check Pivot Position: After partitioning, the pivot is in its final sorted position i.
   • If i == target, you found the element.
   • If i > target, search the left partition.
   • If i < target, search the right partition.
4. Repeat: Continue until the search range narrows to the target index.

# The Intuition

Think of Quickselect as "Goal-Oriented Quicksort". In Quicksort, you are trying to organize the entire room. In Quickselect, you only care about who sits in the $k^{th}$ chair. Once you partition the room, if the $k^{th}$ chair is on the left side, you completely ignore everyone on the right.

Why $O(n)$ and not $O(\log n)$?

• Level 1: Scan $n$ elements.
• Level 2: Scan $n/2$ elements.
• Level 3: Scan $n/4$ elements.
• Sum: $n(1 + 1/2 + 1/4 + \dots) \approx 2n$, which is $O(n)$.

# Complexity

# Time Complexity

Average case is linear because the problem size reduces geometrically. Worst case (highly skewed partitions) is $O(n^2)$, though randomized pivoting makes this nearly impossible in practice.

# Space Complexity

Strictly $O(1)$ if implemented iteratively. Recursive implementations use $O(\log n)$ stack space on average.

# Code

import java.util.Random;
 
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        int target = n - k; // Index in sorted array
        int start = 0, end = n - 1;
        Random rand = new Random();
        
        while (start <= end) {
            // Randomized pivot to prevent O(n^2)
            int pivotIndex = start + rand.nextInt(end - start + 1);
            int pivotPos = partition(nums, start, end, pivotIndex);
            
            if (pivotPos == target) {
                return nums[pivotPos];
            } else if (pivotPos < target) {
                start = pivotPos + 1;
            } else {
                end = pivotPos - 1;
            }
        }
        return -1;
    }
 
    private int partition(int[] nums, int start, int end, int pivotIndex) {
        int pivotValue = nums[pivotIndex];
        swap(nums, pivotIndex, end); // Move pivot to end
        int storeIndex = start;
        
        for (int i = start; i < end; i++) {
            if (nums[i] < pivotValue) {
                swap(nums, i, storeIndex);
                storeIndex++;
            }
        }
        swap(nums, storeIndex, end); // Move pivot to its final place
        return storeIndex;
    }
 
    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

# Caveats

• Modifies Input: Quickselect is an in-place algorithm. If you cannot modify the original array, you must use a Min-Heap ($O(n \log k)$ time, $O(k)$ space).
• Duplicate Elements: Standard partitioning handles duplicates, but very large numbers of identical elements can lead to skewed partitions.
• Worst Case: Always mention that while average is $O(n)$, the theoretical worst case is $O(n^2)$.

# Concepts to Think About

• Min-Heap Approach: Useful if $k$ is very small compared to $n$ or if data is streaming.
• Hoare vs. Lomuto: Hoare's partition uses two pointers from both ends and is generally faster with fewer swaps.
• Median of Medians: The "Introselect" algorithm uses this to ensure $O(n)$ worst-case.
• Introselect: Used in C++ std::nth_element, which switches from Quickselect to Heapsort if recursion goes too deep.

# Logical Follow-up

Question: What if the array is too large to fit in memory? Solution: Use a Min-Heap of size $k$. Iterate through the file, keeping only the $k$ largest elements seen so far in the heap. Space: $O(k)$, Time: $O(n \log k)$.

Question: What if the numbers are in a specific range (e.g., 1 to 1000)? Solution: Use Counting Sort logic. Count frequencies and iterate from 1000 downwards until you hit the $k^{th}$ element. Time: $O(n + Range)$.

# Solution 2 (using heap)

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer&gt; minHeap = new PriorityQueue<&gt;();
 
    for ( int i = 0; i &lt; nums.length; ++i) {
        minHeap.add(nums[i]);
 
        // to ensure we keep the K smallest element
        if (minHeap.size() &gt; k) {
            minHeap.remove();
        }
    }
 
    return minHeap.peek();        
}