#215

Medium

auto_awesomeArray plus Divide and Conquer

LeetCode Problem Workspace

Kth Largest Element in an Array

Find the kth largest element in an unsorted array using optimal approaches like Quickselect or heaps.

array divide and conquer sorting heap priority queue quickselect

Problem Statement

Given an integer array nums and an integer k, you need to return the kth largest element in the array. The array may not be sorted, so you cannot simply access the kth element in sorted order directly.

Consider that this problem involves finding the kth largest element, not the kth distinct one, and challenge yourself to find an efficient solution without fully sorting the array. Think about divide-and-conquer strategies or using heaps for more optimized solutions.

Examples

Example 1

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

Output: 5

Example details omitted.

Example 2

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

Output: 4

Example details omitted.

Constraints

1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104

Solution Approach

Quickselect Algorithm

Quickselect is a variation of Quicksort that can find the kth largest element without sorting the entire array. It partitions the array and recursively works on one side, making it a much more efficient option with an average time complexity of O(n).

Heap-based Approach

Using a min-heap of size k, you can iterate through the array, maintaining the k largest elements seen so far. The root of the heap will be the kth largest element once the array is processed. This approach has a time complexity of O(n log k).

Sorting the Array

A simple but less efficient solution involves sorting the array in descending order and directly accessing the kth element. This has a time complexity of O(n log n), which is generally slower compared to Quickselect or the heap approach for larger arrays.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Quickselect has an average time complexity of O(n) but can degrade to O(n^2) in the worst case. The heap-based approach has a time complexity of O(n log k), making it more efficient when k is much smaller than the array size. Sorting the array takes O(n log n), which is not optimal compared to other methods.

What Interviewers Usually Probe

Does the candidate quickly identify that sorting the array is not the most optimal approach for large arrays?
Can the candidate explain the time complexity trade-offs between Quickselect, heaps, and sorting in terms of real-world performance?
Does the candidate demonstrate an understanding of how to optimize space complexity when working with heaps or Quickselect?

Common Pitfalls or Variants

Common pitfalls

Using a naive sorting approach without considering the more efficient heap or Quickselect methods.
Failing to account for the worst-case time complexity of Quickselect and suggesting it as a one-size-fits-all solution.
Not recognizing that the kth largest element is not necessarily the kth distinct element, leading to misunderstandings about the problem requirements.

Follow-up variants

Finding the kth smallest element in the array instead of the kth largest, which is just a slight modification of the same approach.
Implementing a version where you return the kth largest element in a dynamically changing array, where elements can be added or removed.
Optimizing for memory space when handling very large arrays by considering different heap or Quickselect variants.

FAQ

What is the time complexity of Quickselect for the kth largest element?

Quickselect has an average time complexity of O(n) but can degrade to O(n^2) in the worst case, depending on the choice of pivot.

How do you handle edge cases like arrays with duplicates?

Edge cases with duplicates are handled by considering the array in its entirety. The kth largest element will be determined by the total occurrences, not distinct elements.

Can the kth largest element be negative?

Yes, the kth largest element can be negative if the array contains negative numbers. The solution approaches work with negative values the same way they work with positive ones.

Is the heap-based approach faster than Quickselect?

The heap-based approach has a time complexity of O(n log k), which can be faster than Quickselect when k is small relative to the array size, but Quickselect generally has a better average time complexity of O(n).

When is sorting the array a viable approach?

Sorting the array is a simple approach with a time complexity of O(n log n), but it should be avoided when you need a more efficient solution, especially with larger arrays where Quickselect or heaps are preferred.

terminal

Solution

Solution 1: Quick Select

Quick Select is an algorithm for finding the $k^{th}$ largest or smallest element in an unsorted array. Its basic idea is to select a pivot element each time, dividing the array into two parts: one part contains elements smaller than the pivot, and the other part contains elements larger than the pivot. Then, based on the position of the pivot, it decides whether to continue the search on the left or right side until the $k^{th}$ largest element is found.

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quick_sort(l: int, r: int) -> int:
            if l == r:
                return nums[l]
            i, j = l - 1, r + 1
            x = nums[(l + r) >> 1]
            while i < j:
                while 1:
                    i += 1
                    if nums[i] >= x:
                        break
                while 1:
                    j -= 1
                    if nums[j] <= x:
                        break
                if i < j:
                    nums[i], nums[j] = nums[j], nums[i]
            if j < k:
                return quick_sort(j + 1, r)
            return quick_sort(l, j)

        n = len(nums)
        k = n - k
        return quick_sort(0, n - 1)

Solution 2: Priority Queue (Min Heap)

We can maintain a min heap $\textit{minQ}$ of size $k$, and then iterate through the array $\textit{nums}$, adding each element to the min heap. When the size of the min heap exceeds $k$, we pop the top element of the heap. This way, the final $k$ elements in the min heap are the $k$ largest elements in the array, and the top element of the heap is the $k^{th}$ largest element.

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quick_sort(l: int, r: int) -> int:
            if l == r:
                return nums[l]
            i, j = l - 1, r + 1
            x = nums[(l + r) >> 1]
            while i < j:
                while 1:
                    i += 1
                    if nums[i] >= x:
                        break
                while 1:
                    j -= 1
                    if nums[j] <= x:
                        break
                if i < j:
                    nums[i], nums[j] = nums[j], nums[i]
            if j < k:
                return quick_sort(j + 1, r)
            return quick_sort(l, j)

        n = len(nums)
        k = n - k
        return quick_sort(0, n - 1)

Solution 3: Counting Sort

We can use the idea of counting sort, counting the occurrence of each element in the array $\textit{nums}$ and recording it in a hash table $\textit{cnt}$. Then, we iterate over the elements $i$ from largest to smallest, subtracting the occurrence count $\textit{cnt}[i]$ each time, until $k$ is less than or equal to $0$. At this point, the element $i$ is the $k^{th}$ largest element in the array.

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quick_sort(l: int, r: int) -> int:
            if l == r:
                return nums[l]
            i, j = l - 1, r + 1
            x = nums[(l + r) >> 1]
            while i < j:
                while 1:
                    i += 1
                    if nums[i] >= x:
                        break
                while 1:
                    j -= 1
                    if nums[j] <= x:
                        break
                if i < j:
                    nums[i], nums[j] = nums[j], nums[i]
            if j < k:
                return quick_sort(j + 1, r)
            return quick_sort(l, j)

        n = len(nums)
        k = n - k
        return quick_sort(0, n - 1)

Continue Practicing

#347 top k frequent elements #973 k closest points to origin #324 wiggle sort ii