Kth Largest Element in Array

Today we are going to solve this leetcode problem. In this problem we are required to find the kth largest element in an array of number.

Intutive Approach

This is pretty easy sum if we just sort the array and the return the kth largest element from the array. In python this is pretty easy problme cause in python list can be quried with negative number to return the elements from the end of arrray. For example List[-1] give the last element and list[-2] gives the second last element from the array and so one.

The code looks like this for the obvious approach:

class Solution:
    def kthLargest(self, nums: List[int], k: int) -> int:
        nums.sort()
        return nums[-k]

The time complexity is O(nlog(n)) as the only relevant time is taken while sorting of array. The space complexity is O(n) which is the size of array.

Time Complexity: O(nlog(n))

Space Complexity: O(n)

Using Priority Queue

Now as we know what a priority queue is os if we just use its property then just by running the heappop command for k we can get the kth largest element from the priority queue (Max Heap).

In python heapq provides many functionality for working with heap and its different function, one such is nlargest function that takes k and a list to return the kth largest element, we will use that for the code.

The code will look like this for this qpproach.

import heapq
class Solution:
    def kthLargest(self, nums: List[int], k: int) -> int:
        return heapq.nlargest(k, nums)

Now the time complexity is O(n) as this is the time it takes to make a list heap inplace and space complexity is same previously O(n) as space is same for the storing of list.

Time Complexity: O(n)
Space Complexity: O(n)

If you find any problem with this article or you just want to have chang you can contact me through the the socials.