Kth Largest Element in an Array | LeetCode 215 | Python | Solution

LeetCode 215

From an integer array, we have to find the kth largest element.

I assume that you already know about the sorting algorithms.

We all know how to access an element from an array. If we sort it in descending order, the kth position will be k-1. We all know that an array index starts from 0. That’s why we have to use k-1.

We can use any fast sorting algorithm to achieve this. Let’s see an example.

arr = [2, 1, 8, 3, 4] 
k = 2

sort_algo( [2, 1, 8, 3, 4] )  => [8, 4, 3, 2, 1]

arr[k] => 3 (Wrong Answer)
arr[k-1] => 4 (Right Answer)

Let’s see the solution using the Merge Sort algorithm.

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        
        s = self.merge_sort(nums)
        return s[k-1]
    
    def merge_sort(self, lst):
        
        if len(lst) > 1:
            
            mid = len(lst) // 2
            left = lst[:mid]
            right = lst[mid:]

            self.merge_sort(left)
            self.merge_sort(right)

            i = 0
            j = 0
            k = 0

            while i < len(left) and j < len(right):

                if left[i] > right[j]:
                    lst[k] = left[i]
                    i += 1
                else:
                    lst[k] = right[j]
                    j += 1

                k += 1

            while i < len(left):
                lst[k] = left[i]
                i += 1
                k += 1

            while j < len(right):
                lst[k] = right[j]
                j += 1
                k += 1

        return lst

We can also solve this using python’s built-in sorting function. And also not necessary that we have to sort it in descending order. We can also access an array element from the last.

Let’s see the concise solution using python’s built-in function.

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        
        # s = sorted(nums)
        # return s[-k]
    
        # One Line
        return sorted(nums)[-k]

I hope you got the idea about the problem and the solution concept.

Happy Learning.
Happy Coding.