Kth Largest Element in an Array - Google Interview Question & Solution

Back to All Questions

Kth Largest Element in an Array

Google

Array

Heap

Sorting

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 sorted order, not the kth distinct element.

Example:

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

Solution Walkthrough

Sorting the whole array and reading off the kth-from-the-end element works in O(n log n), but a min-heap of size k does better — O(n log k).

Walk through nums and push each value onto a min-heap.
Whenever the heap grows past size k, pop its minimum — this discards elements that can't possibly be among the k largest.
After processing every element, the heap contains exactly the k largest values, and its root (the minimum of that set) is the answer.

Because the heap never holds more than k elements, each push/pop is O(log k), giving an overall time complexity of O(n log k) and space complexity of O(k).

class MinHeap {
    constructor() { this.data = []; }
    size() { return this.data.length; }
    peek() { return this.data[0]; }

    push(val) {
        this.data.push(val);
        let i = this.data.length - 1;
        while (i > 0) {
            const parent = Math.floor((i - 1) / 2);
            if (this.data[parent] <= this.data[i]) break;
            [this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];
            i = parent;
        }
    }

    pop() {
        const top = this.data[0];
        const last = this.data.pop();
        if (this.data.length > 0) {
            this.data[0] = last;
            let i = 0;
            while (true) {
                const left = 2 * i + 1, right = 2 * i + 2;
                let smallest = i;
                if (left < this.data.length && this.data[left] < this.data[smallest]) smallest = left;
                if (right < this.data.length && this.data[right] < this.data[smallest]) smallest = right;
                if (smallest === i) break;
                [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
                i = smallest;
            }
        }
        return top;
    }
}

function findKthLargest(nums, k) {
    const heap = new MinHeap();
    for (const num of nums) {
        heap.push(num);
        if (heap.size() > k) {
            heap.pop(); // discard the smallest, keeping only the top k
        }
    }
    return heap.peek();
}

Related Algorithms

Min-Heap →

Quick Sort →