Kth largest element in an array

Link: https://leetcode.com/problems/kth-largest-element-in-an-array/

Solution:

Topics: heap

Intuition
Very simple and classic Kth largest/smallest problem. Simply add every number to a min heap and pop off the top when the size of the heap is greater than k. Return the top of the heap at the end of the loop.

Implementation

def kth_largest(nums):
	min_heap = []
	for num in nums:
		heappush(min_heap, num)
		if len(min_heap) > k:
			heappop(min_heap)
	return min_heap[0]
 
#time: o(nlog(k))
#memory: o(k)

Review 1
Too easy.

Review 2
Counting sort can also be used if we create a bucket for every unique number and set it to true when said number is seen. The kth largest would simple then be the kth index of bucket array that is true, from the back.

review