Kth Largest Element IN AN Array

Problem

Write a function that takes an array of unsorted integers nums and an integer k, and returns the kth largest element in the array. This function should run in O(n log k) time, where n is the length of the array.

Example 1

Input:

nums = [5, 3, 2, 1, 4]
k = 2

Output:

Explanation

Approach 1: Sorting

The simplest approach is to sort the array in descending order and return the kth element. This approach has a time complexity of O(n log n) where n is the number of elements in the array, and a space complexity of O(1).

Approach 2: Min Heap

By using a min-heap, we can reduce the time complexity to O(n log k), where n is the number of elements in the array and k is the value of k.

The idea behind this solution is to iterate over the elements in the array while storing the k largest elements we’ve seen so far in a min-heap. At each element, we check if it is greater than the smallest element (the root) of the heap. If it is, we pop the smallest element from the heap and push the current element into the heap. This way, the heap will always contain the k largest elements we’ve seen so far.

After iterating over all the elements, the root of the heap will be the kth largest element in the array.

Solution

def kth_largest(nums, k):
    if not nums:
        return 
    
    heap = []
    for num in nums:
        if len(heap) < k:
            heapq.heappush(heap, num)
        elif num > heap[0]:
            heapq.heappushpop(heap, num)
    
    return heap[0]

public int kthLargest(int[] nums, int k) {
    if (nums.length == 0) {
        return -1;
    }

    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int num : nums) {
        if (heap.size() < k) {
            heap.offer(num);
        } else if (num > heap.peek()) {
            heap.poll();
            heap.offer(num);
        }
    }

    return heap.peek();
}

type IntHeap []int
func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any)         { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any           { o := *h; x := o[len(o)-1]; *h = o[:len(o)-1]; return x }

func kthLargest(nums []int, k int) int {
    if len(nums) == 0 {
        return -1
    }

    h := &IntHeap{}
    for _, num := range nums {
        if h.Len() < k {
            heap.Push(h, num)
        } else if num > (*h)[0] {
            heap.Pop(h)
            heap.Push(h, num)
        }
    }

    return (*h)[0]
}

function heapInsert(heap: number[], val: number) {
    heap.push(val);
    let i = heap.length - 1;
    while (i > 0) {
        const p = (i - 1) >> 1;
        if (heap[p] <= heap[i]) break;
        [heap[p], heap[i]] = [heap[i], heap[p]];
        i = p;
    }
}

function heapReplace(heap: number[], val: number) {
    if (heap.length && heap[0] < val) {
        heap[0] = val;
        let i = 0;
        while (2 * i + 1 < heap.length) {
            let j = 2 * i + 1;
            if (j + 1 < heap.length && heap[j + 1] < heap[j]) j++;
            if (heap[i] <= heap[j]) break;
            [heap[i], heap[j]] = [heap[j], heap[i]];
            i = j;
        }
    }
}

function kthLargest(nums: number[], k: number): number | null {
    if (nums.length === 0) {
        return null;
    }

    const heap: number[] = [];
    for (const num of nums) {
        if (heap.length < k) {
            heapInsert(heap, num);
        } else if (num > heap[0]) {
            heapReplace(heap, num);
        }
    }

    return heap[0];
}