Kth largest/smallest Element in an array

Question

Given an insorted array find the kth smallest element.

Example 1 : 

nums = [7,10,4,3,20,15], k = 3 
result = 10

Example 2:

nums = [7,10,4,3,20,15], k = 4 
result = 7

Reframing the question.

1. If the array is sorted, the kth largest element will be located at len(nums)-(k+1), as arrays start at index 0. Simple enough.
Copy

nums = [ 7, 10, 4, 3, 20, 15], k = 3 
result = 7 

sorted = [3,4,7,10,15,20]
                 ^
k = 3 the value is at index 2

2. However this takes us a time complexity of O(n*log(n)).For sorting.
3. We will use heaps to solve the same problem. All elements will be added to the heap and arranged in a sorted fashion, with the smallest element at the bottom and the largest at the top. This is an illustration of a max heap(max Item on top).

4. Heaps allow us to view the topmost element. How many elements do you want to pop in order to get the kth element on top?


kth	pops
1	0
2	1
3	2
4	3

5. For k = 3, two pops and we can return the top element as the third largest.

6. What are the complexities here?
1. The time complexity is O(n*log(n)),
1. as we insert each element into the heap, which has a complexity of O(log(n)), and we do this n times. The popping is also O(log(n)), and we do it k-1 times. Comes dows to O(n*log(n) + k*log(n)).Since n is greater than k. The total time complexity remains O(n*log(n)).
2. The space complexity is O(n).
3. That is a lot of operations and costly ones at that.
7. We can use the heapify command to create a heap for all the values in the list. Surprisingly, this can be done in O(N). However, there is a slight limitation: we need to know the list beforehand. You don't need to understand the math fully for an interview, but if you are curious, here is a StackOverflow answer.
8. What will be the complexity. O(n + klog(n))Better than before?
9. Can we save iterations by thinking about the problem differently? For example, what if I asked you to get k = 1? That is the same as getting the maximum in the array. Would it make sense to put all the elements in a heap and return the top element or sort the array and return the last element? No, we can simply do a linear search and keep track of the maximum value up until a certain point, updating it as we find a larger maximum. The time complexity of this approach would be O(N). This is our first intution that will help us fit using heap to the nature of the problem.
1. Lets look closer to see what happens with finding the minimum.
2. Imagine the we are keeping track of the max in a bucket.
3. We will only change the value, when we find a larger maximum.
10. k = 2
1. The only sorting we will need to do is between the k elements, we need to keep the max ones on the top?
2. What is the criteria to add it
3. Why use a min heap?

In the next question we will go over the how to identify heaps.

Code