Kth Largest Element in an Array (LC 215)

Pattern: Two Heaps / QuickSelect
Difficulty: Medium
Key Concept: Either maintain a size-k min-heap of the largest values, or partition (QuickSelect) to place the kth largest without full sort.

Problem Statement

Given an integer array nums and an integer k, return the kth largest element in the array.

Notes

• k is 1-indexed in the usual “kth largest” language: k = 1 means the largest element.
• Elements may repeat; duplicates count separately (not “kth distinct”).

Input

• int[] nums
• int k

Output

• int — the kth largest value.

Constraints (typical)

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

Example
nums = [3,2,1,5,6,4], k = 2 → 5 (sorted descending: 6, 5, ...).

---

1. Algorithm & Pseudocode

Brute force (sort)

sort nums in descending order   // or ascending and take index (n - k)
return nums[k - 1]              // if sorted descending

Optimal 1 — Min-heap of size k

pq = empty min-heap
for each x in nums:
  pq.offer(x)
  if pq.size() > k:
    pq.poll()
return pq.peek()

Optimal 2 — QuickSelect (Hoare-style partition)

// Goal: kth largest in nums = element that would sit at index (n - k) if nums were sorted ascending
targetIndex = nums.length - k

quickSelect(nums, 0, nums.length - 1, targetIndex):
  loop:
    p = partition(nums, left, right)   // pivot’s final index
    if p == targetIndex: return nums[p]
    else if p < targetIndex: left = p + 1
    else: right = p - 1

Partition idea
Pick a pivot, rearrange so elements < pivot are left and >= pivot are right (or the mirror variant—stay consistent). Recurse or iterate only on the side that can contain targetIndex.

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Sorting works, but
   Full sort is O(n log n) and uses extra understanding of indexing. Interviewers often ask for something better when k is small relative to n.

2. Min-heap of size k
   Same invariant as LC 703: store the k largest values; the minimum in the heap is the kth largest. Each step is O(log k), total O(n log k). When k << n, this beats O(n log n) sort.

3. QuickSelect intuition
   Like quicksort, but after one partition you only recurse on the half that contains the answer. Average time O(n), but worst case O(n^2) if pivots are bad—mitigate with random pivot.

4. Why targetIndex = n - k?
   In ascending order, the kth largest is the element at position n - k (0-based). Example: n = 6, k = 2 → second largest is index 4 in ascending [1,2,3,4,5,6].

5. Interview tradeoff
   Heap: predictable O(n log k), simple with Java’s PriorityQueue. QuickSelect: faster on average, but worst-case O(n^2) unless randomized—state that clearly.

6. Java Arrays.sort on int[]
   Uses a tuned dual-pivot quicksort for primitives—fast in practice for the brute-force approach.

---

3. The Dry Run

Input: nums = [3, 2, 1, 5, 6, 4], k = 2.
Expected: 5 (largest is 6, second largest is 5).

A) Min-heap of size k = 2

We show heap as multiset (min-heap stores the two largest seen so far; peek = smaller of those two = 2nd largest).

Step	x	Offer into heap	Size	Poll if > 2?	Heap after (values)	peek (2nd largest so far)
1	3	3	1	no	{3}	3
2	2	2,3	2	no	{2,3}	2
3	1	1,2,3	3	poll 1	{2,3}	2
4	5	2,3,5	3	poll 2	{3,5}	3
5	6	3,5,6	3	poll 3	{5,6}	5
6	4	4,5,6	3	poll 4	{5,6}	5

Return peek: 5.

B) QuickSelect (conceptual)

n = 6, k = 2 → targetIndex = n - k = 4 (0-based in ascending sorted array).

Ascending sorted: [1, 2, 3, 4, 5, 6] — index 4 holds 5.

Iteration	Idea	After partition (example)	Compare p to targetIndex (4)
1	Pick pivot, partition	Suppose pivot lands so p = 3	p < 4 → search right half
2	Partition on right	Suppose p = 4	p == 4 → return nums[4]

Actual p depends on pivot choices; the invariant is: when p == 4, the element at index 4 is in its sorted position for ascending order → 5.

---

4. Java Solution

Brute Force

Idea: Sort ascending, return nums[n - k].

Time: O(n log n) Space: O(1) extra if sorting in-place (algorithm may use O(log n) stack depending on implementation).

import java.util.Arrays;

class SolutionBruteForce {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

Optimal

1) Min-heap — O(n log k) time, O(k) space

import java.util.PriorityQueue;

class SolutionHeap {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int x : nums) {
            pq.offer(x);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        return pq.peek();
    }
}

2) QuickSelect — average O(n) time, O(1) extra space (recursion stack O(log n) typical)

import java.util.Random;

class SolutionQuickSelect {
    private static final Random RNG = new Random();

    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        int target = n - k;
        int left = 0;
        int right = n - 1;
        while (true) {
            int p = partition(nums, left, right);
            if (p == target) {
                return nums[p];
            }
            if (p < target) {
                left = p + 1;
            } else {
                right = p - 1;
            }
        }
    }

    private int partition(int[] nums, int left, int right) {
        int pivotIndex = left + RNG.nextInt(right - left + 1);
        swap(nums, pivotIndex, right);
        int pivot = nums[right];
        int store = left;
        for (int i = left; i < right; i++) {
            if (nums[i] <= pivot) {
                swap(nums, store, i);
                store++;
            }
        }
        swap(nums, store, right);
        return store;
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

This partition places pivot at index store such that all elements ≤ pivot are at indices ≤ store (Lomuto-style). The target index is the position of the kth largest in ascending order.

---

5. The “Java vs. Others” Edge

• PriorityQueue: Min-heap by default—direct fit for the size-k pattern. No negation trick needed (unlike Python heapq for “largest”).
• Arrays.sort(int[]): Very fast for the sort-based solution; know it is O(n log n) and not O(n).
• QuickSelect: Java has no nth_element like C++; you implement partition yourself. Random pivot reduces adversarial O(n^2) cases.
• Python: heapq.nlargest(k, nums) is ergonomic; Java uses explicit heap loops.
• Interviews: Mention heap = guaranteed O(n log k) vs QuickSelect = average O(n), worst O(n^2) without randomization.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n log n)	O(1) to O(log n)	Sort ascending; answer at nums[n - k].
Optimal (min-heap k)	O(n log k)	O(k)	Best when k is small; predictable.
Optimal (QuickSelect)	O(n) average, O(n^2) worst	O(1) aux	Random pivot; in-place friendly.