Kth Largest Element in an Array medium

Problem Statement

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

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

Example 2:

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

Steps and Explanation

This problem can be efficiently solved using a min-heap data structure. Here's the breakdown:

1. Min-Heap Initialization: We'll use a min-heap to store the k largest elements encountered so far. A min-heap ensures that the smallest element is always at the root.

2. Iterating through the Array: We iterate through the input array nums.

3. Heap Maintenance: For each element num in nums:

   • If the size of the min-heap is less than k, we add num to the heap. This ensures that we collect the first k elements.
   • If the size of the min-heap is equal to k and num is greater than the smallest element (root) of the heap, we replace the root with num and then "heapify" (re-balance) the heap to maintain the min-heap property. This ensures that we always keep track of the k largest elements seen so far.

4. Returning the Result: After iterating through the entire array, the root of the min-heap will be the kth largest element.

Code (TypeScript)

function findKthLargest(nums: number[], k: number): number {
    // Use a min-heap to store the k largest elements.
    const minHeap = new MinHeap();

    // Iterate through the array.
    for (const num of nums) {
        // Add to heap if less than k elements.
        if (minHeap.size() < k) {
            minHeap.insert(num);
        } else if (num > minHeap.peek()) {
            // Replace smallest if larger than current smallest.
            minHeap.extract();
            minHeap.insert(num);
        }
    }

    // The root of the heap is the kth largest.
    return minHeap.peek();
}


// Min-heap implementation using array.  You could also use a library like priority-queue.
class MinHeap {
    private heap: number[] = [];

    size(): number {
        return this.heap.length;
    }

    peek(): number {
        if (this.heap.length === 0) {
            throw new Error("Heap is empty");
        }
        return this.heap[0];
    }

    insert(value: number): void {
        this.heap.push(value);
        this.heapifyUp(this.heap.length - 1);
    }

    extract(): number {
        if (this.heap.length === 0) {
            throw new Error("Heap is empty");
        }
        const root = this.heap[0];
        this.heap[0] = this.heap.pop()!; //swap last element with root and pop off the last
        this.heapifyDown(0);
        return root;
    }

    private heapifyUp(index: number): void {
        let currentIndex = index;
        while (currentIndex > 0) {
            const parentIndex = Math.floor((currentIndex - 1) / 2);
            if (this.heap[currentIndex] < this.heap[parentIndex]) {
                [this.heap[currentIndex], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[currentIndex]];
                currentIndex = parentIndex;
            } else {
                break;
            }
        }
    }

    private heapifyDown(index: number): void {
        let currentIndex = index;
        while (true) {
            let smallestIndex = currentIndex;
            const leftChildIndex = 2 * currentIndex + 1;
            const rightChildIndex = 2 * currentIndex + 2;

            if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] < this.heap[smallestIndex]) {
                smallestIndex = leftChildIndex;
            }
            if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] < this.heap[smallestIndex]) {
                smallestIndex = rightChildIndex;
            }

            if (smallestIndex !== currentIndex) {
                [this.heap[currentIndex], this.heap[smallestIndex]] = [this.heap[smallestIndex], this.heap[currentIndex]];
                currentIndex = smallestIndex;
            } else {
                break;
            }
        }
    }
}

Complexity Analysis

• Time Complexity: O(N log k), where N is the length of the input array. Building the heap initially takes O(k log k) time, and iterating through the remaining elements takes O((N-k) log k). In the worst case, where k is close to N, this simplifies to O(N log N). If k is significantly smaller than N, this approaches O(N log k) which is much better.

• Space Complexity: O(k) to store the min-heap. The space used by the heap is proportional to k.