Array Processing with Priority Queue
Filed under Microsoft
Free read 3 of 3Determine if elements can have duplicates and whether memory constraints restrict storing the entire array in a heap.
The question
Solve an array manipulation problem efficiently using a priority queue or heap approach.
Constraints
- Array size up to 10^5 elements
- Time limit strictness requires O(n log k) or better
Examples
- Input
- nums = [3,2,1,5,6,4], k = 2
- Output
- 5
- Why
- Finds the 2nd largest element using a min-heap of size k.
Approach
Determine if elements can have duplicates and whether memory constraints restrict storing the entire array in a heap.
Sort the entire array and retrieve the target element, taking O(n log n) time.
Use a min-heap (or priority queue) to maintain the top k elements dynamically as you iterate through the array, reducing time complexity to O(n log k).
Handle edge cases where k is out of bounds or the array contains negative numbers.
Solution
O(n log k) time, O(k) space
import heapq
def find_kth_largest(nums: list[int], k: int) -> int:
min_heap = []
for num in nums:
heapq.heappush(min_heap, num)
if len(min_heap) > k:
heapq.heappop(min_heap)
return min_heap[0]
Tips
- What they are testing: Test with duplicate elements, k equals 1, and k equals the array length.
- Common mistake: Using a max-heap for finding the k-th largest element when a min-heap of size k is more space-efficient.
Related Microsoft questions
Collected from public candidate posts and coding forums. Updated Nov 2026.