LeetMotion
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Follow-up: Can you solve it without sorting?
1 <= k <= nums.length <= 10000-10000 <= nums[i] <= 10000Why do it this way? The most direct answer to "what is the Kth largest?" is to put everything in order and pick the Kth one from the end! While easy to write in one line of code, this takes O(N log N) time, which does a lot of unnecessary work fully sorting elements we don't care about.
If you only need to know who got 2nd place (the 2nd largest), you don't need to strictly rank the 89th and 90th place competitors. Sorting forces you to rank absolutely everyone just to find the top few.
function findKthLargest(nums, k):
nums.sort()
return nums[len(nums) - k]Why do it this way? We only care about the top k elements. If we maintain a Min-Heap of exactly size k, the smallest of the top k elements sits right at the root. We stream numbers in: if the heap grows larger than k, we pop the root. The root is effectively the "worst of the best". At the end, the root is exactly our answer.
Imagine a gaming tournament with exactly k chairs on the winner's stage. The person with the lowest score currently on stage is placed in the "worst chair". When a new player arrives, we compare them to the person in the worst chair. If they score higher, the worst chair is kicked out (popped), and the new player takes a seat!
function findKthLargest(nums, k):
minHeap = []
for num in nums:
heappush(minHeap, num)
if minHeap.size > k:
heappop(minHeap)
return minHeap[0]Why do it this way? The Kth largest element is exactly the element that would sit at index len(nums) - k if the array were fully sorted. Quick Select is an algorithm that can find the element at a specific sorted index without actually sorting the whole array. By randomly partitioning the array like QuickSort, but only recurring on the side that contains our target index, we achieve average O(N) time!
You pick a random person (pivot). You put everyone shorter than them on the left, and everyone taller on the right. If exactly one person is on the right, you know the pivot is the 2nd tallest person! You didn't have to sort anyone, you just grouped them by comparison.
function findKthLargest(nums, k):
target_idx = len(nums) - k
function quickSelect(l, r):
pivot = nums[r]
p = l
for i from l to r-1:
if nums[i] <= pivot:
swap(nums[p], nums[i])
p += 1
swap(nums[p], nums[r]) // place pivot
if p > target_idx: return quickSelect(l, p - 1)
if p < target_idx: return quickSelect(p + 1, r)
return nums[p]
return quickSelect(0, len(nums) - 1)Why do it this way? The classic Quick Select can degrade to O(N²) time if the pivot chosen is consistently the largest or smallest element (e.g., if the array is already sorted!). This optimal version avoids the worst-case scenario by using a "Median-of-Three" pivot selection. It intelligently picks the median of the first, middle, and last elements to ensure the array splits evenly. It also uses two pointers scanning inward to partition elements more efficiently.
Imagine picking a person to split a line by height. If you blindly pick the first person every time, you might accidentally pick the tallest person, making everyone go to the left line, which doesn't help you divide the group! Instead, you quickly grab three random people, pick the one with middle height, and use them as the judge. This guarantees a much fairer split every time.
The problem asks for the k-th largest element, not the k-th smallest. When using sorting, the k-th largest is at index n - k, not at index k - 1. Similarly, in QuickSelect, you must convert to the correct target index. Mixing up these indices is a very common source of off-by-one errors.
For the heap approach, a min-heap of size k is the correct choice because it keeps the smallest of the k largest elements at the top. Using a max-heap would require storing all n elements and extracting k times, which is less efficient. The min-heap approach maintains O(k) space and O(n log k) time.
QuickSelect degrades to O(n²) time when the pivot choice is consistently poor, such as always picking the last element on an already sorted or reverse-sorted array. This can cause Time Limit Exceeded errors. Using randomized pivot selection or median-of-three pivot selection helps avoid this worst case and keeps the average complexity at O(n).
Discussion
…