Crack the Backend

Problem Statement

Given an integer array nums and an integer k, return the k-th largest element in the array. Note: this is the k-th largest in sorted order, not the k-th distinct element (e.g. the 2nd largest in [3,2,1,2] could be 2).

Key Observations

Min-heap of size k: Maintain a min-heap containing exactly the k largest elements seen so far. For each x: if heap size < k, add x; else if x > heap.peek(), remove the minimum and add x. The root of the heap is the k-th largest. Time O(n log k), space O(k).
Quickselect: Partition by a pivot; if pivot position equals n-k we're done; else recurse on left or right. O(n) average.

Approach

High-level: Min-heap (PriorityQueue). For each x: if size < k offer(x); else if x > peek() { poll(); offer(x); } return peek().

Steps: PriorityQueue<Integer> pq = new PriorityQueue<>(); for (int x : nums) { if (pq.size() < k) pq.offer(x); else if (x > pq.peek()) { pq.poll(); pq.offer(x); } } return pq.peek();

Implementation

Java

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

Test Cases

Example 1

Input

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

Expected

5

Explanation

2nd largest is 5.

Complexity Analysis

Time: typically O(n log k) or O(n log n).
Space: O(k) or O(n).

Follow-ups

Stream: process one element at a time.