215. Kth Largest Element in an Array Medium

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 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

Approach

Input: Integer array nums and integer k

Output: The kth largest element in the array

Method Analysis

• Direct sorting takes O(n log n) time complexity, which does not meet the optimal solution desired by the problem.
• We can use a Min Heap to reduce the complexity.

Specific Walkthrough

1. Implement a min heap MiniHeap.
2. Iterate through the array elements:
   • If the size of the heap is less than k, push it directly.
   • If the size of the heap equals k and the current element is greater than the top of the heap (the minimum value), replace the heap top with this element and sift down.
3. After the iteration ends, the heap will retain the largest k elements.
4. The top element of the heap is the kth largest number.

Complexity Analysis

• Each heap operation takes O(log k), processing n elements in total.
• Total Time Complexity: O(n log k)
• Space Complexity: O(k)

Implementation

python

import heapq
from typing import List

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # Convert the input list nums into a min heap
        # heapq.heapify modifies the list in-place into a heap
        heapq.heapify(nums)

        # Continually pop the top element until only k elements remain in the heap
        # Because it is a min heap, the remaining top element will be the kth largest element overall
        while len(nums) > k:
            heapq.heappop(nums)
        
        # Return the top element of the heap, which is the kth largest element
        return nums[0]

javascript

// Define a Min Heap class
class MiniHeap {
    constructor() {
        this.data = [];  // Array to store the heap, following a complete binary tree structure
    }

    // Return the top element (minimum value)
    peek() { return this.data[0]; }

    // Return the number of elements in the heap
    size() { return this.data.length; }

    // Insert an element
    push(val) {
        this.data.push(val);                 // Place the new element at the end of the array (bottom right of the tree)
        this._siftUp(this.size() - 1);       // Adjust upwards to restore min heap property
    }

    // Remove and return the top element (minimum value)
    pop() {
        if (this.size() === 0) return null;  // Return null if heap is empty

        const top = this.data[0];            // Record the top
        const last = this.data.pop();        // Remove the last element of the array

        if (this.size() > 0) {
            this.data[0] = last;             // Put the last element to the top
            this._siftDown(0);               // Adjust downwards to restore heap order
        }

        return top;                          // Return the minimum value
    }

    // Replace the top element (more efficient than pop followed by push)
    replaceTop(val) {
        this.data[0] = val;                  // Override the top directly
        this._siftDown(0);                   // Sift down to restore heap order
    }

    // Sift up operation: used during insertion
    _siftUp(i) {
        while (i > 0) {
            const parent = Math.floor((i - 1) / 2); // Parent node index
            if (this.data[i] >= this.data[parent]) break; // Min heap property satisfied, no adjustment needed

            // Otherwise swap with parent and continue moving up
            [this.data[i], this.data[parent]] = [this.data[parent], this.data[i]];
            i = parent;
        }
    }

    // Sift down operation: used when popping/replacing top
    _siftDown(i) {
        const n = this.size();
        while (true) {
            let smallest = i;               // Initially assume the current node is the smallest
            const left = i * 2 + 1;         // Left child index
            const right = left + 1;         // Right child index

            // If left child is smaller, update smallest
            if (left < n && this.data[left] < this.data[smallest]) smallest = left;
            // If right child is smaller, update smallest
            if (right < n && this.data[right] < this.data[smallest]) smallest = right;

            if (smallest === i) break;      // Already satisfied min heap property, no adjustment needed

            // Otherwise swap and continue moving down
            [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
            i = smallest;
        }
    }
}


/**
 * Main function: Find the kth largest element in the array
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    const heap = new MiniHeap();  // Define a min heap

    // Iterate over the array
    for (let x of nums) {
        if (heap.size() < k) {
            // If the heap size is less than k, push directly
            heap.push(x);
        } else {
            // If the heap is full and the current element is greater than the top of the heap
            // It means it's more "qualified" to enter the top k
            if (x > heap.peek()) {
                heap.replaceTop(x);  // Replace the moving minimum overall recorded
            }
        }
    }

    // After iteration, the heap retains the largest k numbers
    // The top of the heap is the smallest among them, which translates literally to "kth largest"
    return heap.peek();
};

Complexity Analysis

• Time Complexity: O(n log k)
• Space Complexity: O(k)

Links

215. Kth Largest Element in an Array (English)

215. 数组中的第K个最大元素 (Chinese)