215. Kth Largest Element In An Array - Explanation

Description

Given an unsorted array of integers nums and an integer k, return the kth largest element in the array.

By kth largest element, we mean the kth largest element in the sorted order, not the kth distinct element.

Follow-up: Can you solve it without sorting?

Example 1:

Input: nums = [2,3,1,5,4], k = 2

Output: 4

Example 2:

Input: nums = [2,3,1,1,5,5,4], k = 3

Output: 4

Constraints:

1 <= k <= nums.length <= 10000
-1000 <= nums[i] <= 1000

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(nlogk) time and O(k) space, where n is the size of the input array, and k represents the rank of the largest number to be returned (i.e., the k-th largest element).

Hint 1

A naive solution would be to sort the array in descending order and return the k-th largest element. This would be an O(nlogn) solution. Can you think of a better way? Maybe you should think of a data structure which can maintain only the top k largest elements.

Hint 2

We can use a Min-Heap, which stores elements and keeps the smallest element at its top. When we add an element to the Min-Heap, it takes O(logk) time since we are storing k elements in it. Retrieving the top element (the smallest in the heap) takes O(1) time. How can this be useful for finding the k-th largest element?

Hint 3

The k-th largest element is the smallest element among the top k largest elements. This means we only need to maintain k elements in our Min-Heap to efficiently determine the k-th largest element. Whenever the size of the Min-Heap exceeds k, we remove the smallest element by popping from the heap. How do you implement this?

Hint 4

We initialize an empty Min-Heap. We iterate through the array and add elements to the heap. When the size of the heap exceeds k, we pop from the heap and continue. After the iteration, the top element of the heap is the k-th largest element.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Sorting

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

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

2. Min-Heap

class Solution:
    def findKthLargest(self, nums, k):
        return heapq.nlargest(k, nums)[-1]

Time & Space Complexity

Time complexity: $O(n \log k)$
Space complexity: $O(k)$

Where $n$ is the length of the array $nums$ .

3. Quick Select

class Solution:

    def findKthLargest(self, nums: List[int], k: int) -> int:
        k = len(nums) - k

        def quickSelect(l, r):
            pivot, p = nums[r], l
            for i in range(l, r):
                if nums[i] <= pivot:
                    nums[p], nums[i] = nums[i], nums[p]
                    p += 1
            nums[p], nums[r] = nums[r], nums[p]

            if p > k:
                return quickSelect(l, p - 1)
            elif p < k:
                return quickSelect(p + 1, r)
            else:
                return nums[p]

        return quickSelect(0, len(nums) - 1)

Time & Space Complexity

Time complexity: $O(n)$ in average case, $O(n ^ 2)$ in worst case.
Space complexity: $O(n)$

4. Quick Select (Optimal)

class Solution:
    def partition(self, nums: List[int], left: int, right: int) -> int:
        mid = (left + right) >> 1
        nums[mid], nums[left + 1] = nums[left + 1], nums[mid]

        if nums[left] < nums[right]:
            nums[left], nums[right] = nums[right], nums[left]
        if nums[left + 1] < nums[right]:
            nums[left + 1], nums[right] = nums[right], nums[left + 1]
        if nums[left] < nums[left + 1]:
            nums[left], nums[left + 1] = nums[left + 1], nums[left]

        pivot = nums[left + 1]
        i = left + 1
        j = right

        while True:
            while True:
                i += 1
                if not nums[i] > pivot:
                    break
            while True:
                j -= 1
                if not nums[j] < pivot:
                    break
            if i > j:
                break
            nums[i], nums[j] = nums[j], nums[i]

        nums[left + 1], nums[j] = nums[j], nums[left + 1]
        return j

    def quickSelect(self, nums: List[int], k: int) -> int:
        left = 0
        right = len(nums) - 1

        while True:
            if right <= left + 1:
                if right == left + 1 and nums[right] > nums[left]:
                    nums[left], nums[right] = nums[right], nums[left]
                return nums[k]

            j = self.partition(nums, left, right)

            if j >= k:
                right = j - 1
            if j <= k:
                left = j + 1

    def findKthLargest(self, nums: List[int], k: int) -> int:
        return self.quickSelect(nums, k - 1)

Time & Space Complexity

Time complexity: $O(n)$ in average case, $O(n ^ 2)$ in worst case.
Space complexity: $O(1)$