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

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

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

1) Explain the problem

You are given an integer array nums and an integer k. Your task is to find the kth largest element in the array without sorting the entire array. The kth largest element is the element that would be in the kth position if the array were sorted in descending order.

2) Short easy to remember solution/approach

Use a min heap (priority queue) to keep track of the k largest elements seen so far. The root of the min heap will be the kth largest element once we've processed the entire array.

3) Solution in JavaScript with code commenting

// Helper function to create a min heap
class MinHeap {
    constructor() {
        this.heap = [];
    }

    // Insert a new element into the heap
    insert(val) {
        this.heap.push(val);
        this._heapifyUp();
    }

    // Remove and return the min element (root) of the heap
    extractMin() {
        if (this.size() === 0) return null;
        if (this.size() === 1) return this.heap.pop();
        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._heapifyDown();
        return min;
    }

    // Get the size of the heap
    size() {
        return this.heap.length;
    }

    // Get the min element (root) of the heap without removing it
    peek() {
        return this.heap[0];
    }

    // Internal method to maintain heap property after insertion
    _heapifyUp() {
        let index = this.heap.length - 1;
        while (index > 0) {
            let parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[index] >= this.heap[parentIndex]) break;
            [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
            index = parentIndex;
        }
    }

    // Internal method to maintain heap property after extraction
    _heapifyDown() {
        let index = 0;
        while (true) {
            let leftChildIndex = 2 * index + 1;
            let rightChildIndex = 2 * index + 2;
            let smallest = index;

            if (leftChildIndex < this.size() && this.heap[leftChildIndex] < this.heap[largest]) {
                smallest = leftChildIndex;
            }
            if (rightChildIndex < this.size() && this.heap[rightChildIndex] < this.heap[largest]) {
                smallest = rightChildIndex;
            }
            if (smallest === index) break;
            [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
            index = smallest;
        }
    }
}

// Function to find the kth largest element in the array
function findKthLargest(nums, k) {
    const minHeap = new MinHeap();

    // Insert the first k elements into the min heap
    for (let i = 0; i < k; i++) {
        minHeap.insert(nums[i]);
    }

    // Iterate over the remaining elements
    for (let i = k; i < nums.length; i++) {
        if (nums[i] > minHeap.peek()) {
            minHeap.extractMin();
            minHeap.insert(nums[i]);
        }
    }

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

4) Explanation of the solution in an easy-to-understand way

Imagine you have a list of numbers and you want to find the kth largest one without sorting the whole list. You use a special basket that always keeps the smallest number on top. You add the first k numbers to this basket. Then, for every new number, you check if it's bigger than the smallest number in the basket. If it is, you replace the smallest number with the new number. In the end, the smallest number in the basket is your kth largest number.

5) Code explanation in pointers

MinHeap class creates a min heap to manage the k largest elements efficiently.
findKthLargest function:
- Inserts the first k elements into the min heap.
- Iterates over the remaining elements, replacing the smallest element in the heap if the current element is larger.
- Returns the smallest element in the heap, which is the kth largest element.

6) Complexities

Time Complexity: O(n log k), where n is the number of elements in the array and k is the number of largest elements to keep track of. This is because inserting and extracting from the heap takes O(log k) time, and we do this for each of the n elements.
Space Complexity: O(k), where k is the number of largest elements to keep track of. This is due to the space required to store the k largest elements in the heap.

Why a Min Heap is More Efficient

Maintaining k Largest Elements:
- Min Heap: We only need to keep track of the k largest elements. The min heap allows us to efficiently maintain these k elements by keeping the smallest of the k largest at the root. This way, when a new element is larger than the smallest of the k largest, we replace it.
- Max Heap: If we used a max heap, we would have to maintain all elements and then perform multiple extract operations to find the kth largest element. This would require more space and more operations.

Example to Illustrate

Consider the array [3, 2, 1, 5, 6, 4] and k = 2.

Step-by-Step Process with Min Heap:
- Insert first k elements [3, 2] into the min heap.
- The min heap now contains [2, 3] with 2 as the root (smallest).
- Process remaining elements:
  - 1: not larger than 2, so ignored.
  - 5: larger than 2, replace 2 with 5. Heap becomes [3, 5].
  - 6: larger than 3, replace 3 with 6. Heap becomes [5, 6].
  - 4: not larger than 5, so ignored.
- The min heap now contains the two largest elements [5, 6].
- The root of the min heap (5) is the 2nd largest element.

This efficient approach ensures that we only keep track of the necessary k elements, providing an optimal solution for finding the kth largest element.

Kth Largest Element in an Array (Medium)