Leetcode 215 Solution

This article provides solution to leetcode question 215 (kth-largest-element-in-an-array)
Categories:
Tags:
Access this page by simply typing in "lcs 215" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        l = 0
        r = len(nums) - 1
        k -= 1

        while True:
            if k == 0 and l == r:
                return nums[l]

            rand_idx = random.randint(l, r)
            nums[rand_idx], nums[r] = nums[r], nums[rand_idx]

            i, j = l, l

            while j <= r:
                if nums[j] >= nums[r]:
                    nums[i], nums[j] = nums[j], nums[i]
                    i += 1
                j += 1

            i -= 1

            if k < i - l:
                r = i - 1
            elif k > i - l:
                k = k - (i - l) - 1
                l = i + 1
            else:
                return nums[i]