Kth Largest Element In An Array

MEDIUM✓ CHIP-TIMEDLC #215 — FULL STATEMENT ↗

The drill: Find the kth biggest value in an unsorted array — k=1 is the max, but any k should come back without fully sorting everything first.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An unsorted array of integers arrives along with a rank k, and the task is naming the kth biggest value if the whole array were sorted in descending order.

k=1 asks for the plain maximum, but any k in range should come back without necessarily sorting the entire array first — the array's own order is otherwise irrelevant, only the one answer matters.

Duplicate values are counted by position, not collapsed — a repeated value occupies its own separate slot in the ranking, the same as any other value would.

EX 01

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

→ 5

THE BOARD'S SHAPE, UNSORTED INPUT

EX 02

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

→ 4

DUPLICATES THROUGHOUT

EX 03

nums = [1] · k = 1

→ 1

MINIMUM SIZE, K=1

k always falls within the array's length
array sizes run up to tens of thousands of elements
values can repeat and be negative, zero, or positive
duplicates occupy separate ranks, not a single shared one

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A full sort answers this immediately, but it also ranks every element the question never asked about — think about how little of the array actually decides the kth-largest answer.

HINT 2 THE STRUCTURE

Only the k largest values ever matter, and among just those k, the smallest one is exactly the answer being asked for.

HINT 3 ONE STEP FROM THE ANSWER

Keep a min-heap capped at size k as you scan the array: push each value, pop the smallest once the heap overflows past k. When the scan ends, the heap's top is the kth largest.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE ROOT IS THE ANSWERPATTERN · MIN-HEAP OF SIZE Knums = [3, 2, 1, 5, 6, 4] · k = 2

THE HEAP (SIZE ≤ K)

— empty —

STEP 1

k=2. Scan once, keeping a min-heap capped at size 2 — its root always holds the 2nd largest seen so far.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/kth-largest-element-in-an-array.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for v in nums:
            heapq.heappush(heap, v)
            if len(heap) > k:
                heapq.heappop(heap)
        return heap[0]

TIME O(N LOG K)SPACE O(K)PYTHON · RACE PACE · 8 LN

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

TIME O(N LOG K)SPACE O(K)JAVA · RACE PACE · 12 LN

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

TIME O(N LOG N)SPACE O(LOG N)JAVA · TRAINING PACE · 7 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED