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

Approach: Min-Heap of Size k

Algorithm

1. Maintain a min-heap of size k
2. For each element, add it to the heap
3. If the heap size exceeds k, remove the smallest element (the root)
4. After processing all elements, the heap contains the k largest elements; the root is the kth largest

Time & Space Complexity

• Time Complexity: O(n log k) - each heap operation costs O(log k)
• Space Complexity: O(k) - heap storage

Java Implementation

import java.util.PriorityQueue;

public class KthLargestElementInAnArray {

    /**
     * Return the kth largest element in the array.
     * @param nums Input array
     * @param k Rank (1-based)
     * @return kth largest element
     */
    public static 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();
    }

    // Test method
    public static void main(String[] args) {
        int[] nums1 = {3, 2, 1, 5, 6, 4};
        int k1 = 2;
        System.out.println("Input: nums = [3, 2, 1, 5, 6, 4], k = 2");
        System.out.println("Output: " + findKthLargest(nums1, k1)); // Expected: 5

        int[] nums2 = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        int k2 = 4;
        System.out.println("Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4");
        System.out.println("Output: " + findKthLargest(nums2, k2)); // Expected: 4
    }
}

Alternative Approach: Quickselect (O(n) Average)

Use the partition step from quick sort to narrow down which half contains the kth largest element, discarding the other half each round.

public class KthLargestElementQuickselect {

    public static int findKthLargest(int[] nums, int k) {
        // kth largest is the (n - k)th smallest
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }

    private static int quickSelect(int[] nums, int lo, int hi, int target) {
        int pivot = nums[hi];
        int i = lo;

        for (int j = lo; j < hi; j++) {
            if (nums[j] <= pivot) {
                swap(nums, i, j);
                i++;
            }
        }
        swap(nums, i, hi);

        if (i == target) {
            return nums[i];
        } else if (i < target) {
            return quickSelect(nums, i + 1, hi, target);
        } else {
            return quickSelect(nums, lo, i - 1, target);
        }
    }

    private static void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

Key Points

1. Duplicates Count: The kth largest counts repeated values (not distinct)
2. Min-Heap Trick: Keeping only k elements in a min-heap leaves the kth largest at the top
3. No Sorting: Both the heap and quickselect approaches avoid a full O(n log n) sort
4. Quickselect: O(n) average time, O(n²) worst case
5. Equivalent Formulation: kth largest = (n - k)th smallest