How to Solve Kth Largest Element in an Array on LeetCode
The Kth Largest Element in an Array problem is a LeetCode favorite that evaluates your grasp of selection algorithms, heaps, and efficient array manipulation.
Problem Statement
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 sorted order, not the kth distinct element.
Example:
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Why This Problem Matters for Interviews
This problem:
- Tests your knowledge of selection algorithms (Quickselect)
- Assesses heap data structure skills
- Emphasizes optimal vs brute force approaches
Approaches to Kth Largest Element in an Array
1. Heap (Optimal for Small k)
Use a min-heap of size k.
Time Complexity: O(n log k)
Space Complexity: O(k)
import heapq
def findKthLargest(nums: list[int], k: int) -> int:
heap = nums[:k]
heapq.heapify(heap)
for n in nums[k:]:
if n > heap[0]:
heapq.heapreplace(heap, n)
return heap[0]
2. Quickselect (Average O(n))
Partition-based selection like quicksort.
Time Complexity: O(n) average, O(n^2) worst case
Space Complexity: O(1)
import random
def findKthLargest(nums: list[int], k: int) -> int:
def quickselect(left, right, k_smallest):
if left == right:
return nums[left]
pivot_idx = random.randint(left, right)
nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
store_idx = left
for i in range(left, right):
if nums[i] > nums[right]:
nums[store_idx], nums[i] = nums[i], nums[store_idx]
store_idx += 1
nums[store_idx], nums[right] = nums[right], nums[store_idx]
if store_idx == k_smallest:
return nums[store_idx]
elif store_idx < k_smallest:
return quickselect(store_idx + 1, right, k_smallest)
else:
return quickselect(left, store_idx - 1, k_smallest)
return quickselect(0, len(nums) - 1, k - 1)
Key Interview Talking Points
- Why sorting is O(n log n) and suboptimal
- Heap vs Quickselect tradeoffs
- Edge cases: duplicates, k = 1 or k = len(nums)
- Quickselect's worst-case behavior
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Heap | O(n log k) | O(k) |
| Quickselect | O(n) avg / O(n^2) wc | O(1) |
Pro Interview Tips
- Explain why min-heap is used for kth largest.
- Discuss in-place vs extra space approaches.
- Practice with test cases