215. Kth Largest Element in an Array

Description of Problem

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

Constraints:

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

Solution

Tags: Heap

Explanation

Use a bounded-sized min-heap to store element and pop the top element when the size of heap is greater than k.

Code (Rust)

impl Solution {
    pub fn find_kth_largest(nums: Vec<i32>, k: i32) -> i32 {
        use std::collections::BinaryHeap;
        use std::cmp::Reverse;

        let mut heap = BinaryHeap::new();
        let k = k as usize;

        for n in nums.into_iter(){
            heap.push(Reverse(n));
            if heap.len() > k {
                heap.pop();
            }
        }

        return heap
            .pop()
            .expect("Should have at least one element in heap")
            .0;
    }

}

Complexity

• n is length of nums

Time Complexity

• \( T(n,k) = \Theta( n \cdot (\lg k + 1) ) \)

Auxiliary Space

• \( S(n,k) = \Theta( k ) \)