Kth Largest Element in an Array

Problem Statement

Find the kth largest element in an unsorted array. This can be solved efficiently using a QuickSelect algorithm, a variation of Quick Sort.

Example

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

Output: 5 (the 2nd largest element)

Code

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }

    private int quickSelect(int[] nums, int left, int right, int k) {
        if (left == right) return nums[left];
        
        int pivotIndex = partition(nums, left, right);
        
        if (k == pivotIndex) {
            return nums[k];
        } else if (k < pivotIndex) {
            return quickSelect(nums, left, pivotIndex - 1, k);
        } else {
            return quickSelect(nums, pivotIndex + 1, right, k);
        }
    }

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

def find_kth_largest(nums, k):
    def quick_select(left, right, k_smallest):
        if left == right:
            return nums[left]
        
        pivot_index = partition(left, right)
        
        if k_smallest == pivot_index:
            return nums[k_smallest]
        elif k_smallest < pivot_index:
            return quick_select(left, pivot_index - 1, k_smallest)
        else:
            return quick_select(pivot_index + 1, right, k_smallest)
    
    def partition(left, right):
        pivot = nums[right]
        i = left - 1
        
        for j in range(left, right):
            if nums[j] <= pivot:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]
        
        nums[i + 1], nums[right] = nums[right], nums[i + 1]
        return i + 1
    
    return quick_select(0, len(nums) - 1, len(nums) - k)

# Example usage
print(find_kth_largest([3, 2, 1, 5, 6, 4], 2))  # 5
            

function findKthLargest(nums, k) {
    function quickSelect(left, right, kSmallest) {
        if (left === right) return nums[left];
        
        let pivotIndex = partition(left, right);
        
        if (kSmallest === pivotIndex) {
            return nums[kSmallest];
        } else if (kSmallest < pivotIndex) {
            return quickSelect(left, pivotIndex - 1, kSmallest);
        } else {
            return quickSelect(pivotIndex + 1, right, kSmallest);
        }
    }

    function partition(left, right) {
        let pivot = nums[right];
        let i = left - 1;
        
        for (let j = left; j < right; j++) {
            if (nums[j] <= pivot) {
                i++;
                [nums[i], nums[j]] = [nums[j], nums[i]];
            }
        }
        
        [nums[i + 1], nums[right]] = [nums[right], nums[i + 1]];
        return i + 1;
    }
    
    return quickSelect(0, nums.length - 1, nums.length - k);
}

// Example usage
console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2)); // 5
            

Explanation

• Use QuickSelect to partition the array around a pivot.
• Determine if the kth element is in the left or right partition.
• Recursively search only the relevant partition.
• Stop when the pivot index matches the desired position.

Note