Algorithm Day75 - Kth Largest Element in an Array

Posted on In , , Views:

🧩 Problem Description

Given an 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 the sorted order, not the k-th distinct element.

💬 Examples

Example 1

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

Example 2

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

💡 Intuition

There are two common approaches:

  1. Heap (Min-Heap of size k):

    • Maintain a heap of the largest k elements.
    • The root of the heap is the answer.
    • Time: O(n log k).

  2. Quickselect (Hoare’s selection algorithm):

    • Similar to quicksort partitioning.
    • Average time: O(n), worst-case O(n²).
    • More efficient in practice.

🔢 Java Code (Heap)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;

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();
    }
}

🔢 Java Code (Quickselect)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        return quickSelect(nums, 0, n - 1, n - k);
    }
    
    private int quickSelect(int[] nums, int left, int right, int k) {
        int pivot = nums[right];
        int p = left;
        for (int i = left; i < right; i++) {
            if (nums[i] <= pivot) {
                swap(nums, i, p);
                p++;
            }
        }
        swap(nums, p, right);
        
        if (p == k) return nums[p];
        else if (p < k) return quickSelect(nums, p + 1, right, k);
        else return quickSelect(nums, left, p - 1, k);
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

⏱ Complexity Analysis

Heap Solution

  • Time: O(n log k)
  • Space: O(k)

Quickselect Solution

  • Time: O(n) on average, O(n²) worst-case
  • Space: O(1)

✍️ Summary

  • Use min-heap for simplicity.
  • Use quickselect for optimal performance on average.

Related problems

  • lc-347 — Top K Frequent Elements
  • lc-973 — K Closest Points to Origin
  • lc-703 — Kth Largest Element in a Stream