Skip to main content

Kth Largest Element In An Array

Question​

Two bar problem​

find best area among ....

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

You must solve it in O(n) time complexity.

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

""" Time Complexity: O(nlogk); in the worst case, adding or removing an element from a heap will take O(logk) time because our heap will be size k at most. We potentially need to do this for every element in nums hence why we multiply this operation by n which gives us O(nlogk).

Space Complexity: O(k); in the worst case, our heap will be size k """

Solution​

heap/Kth Largest Element in an Array.py
import heapq

def largest(nums, k):
    h = []

    for n in nums:
        heapq.heappush(h, -1*n)

    for i in range(k):
        #print(h)
        n = heapq.heappop(h)

    return -1*n


result = largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)
# print(largest([3, 2, 1, 5, 6, 4], 2))

#print(result)
Steph
1[-3, -2, -3, -2, -1]
2[-3, -2, -3, -2, -1]
3[-3, -2, -3, -2, -1]
4[-3, -2, -3, -2, -1]
result
4