MEDIUM NC#67 Heap / Priority Queue
215. Kth Largest Element in an Array
📖 Problem
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. Can you solve it without sorting?
🧠 Visual Learning Aid
1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases
JS/TS Refreshers
- •Array methods (`push`, `pop`, `shift`, `slice`)
- •Object/Map/Set usage patterns
- •Function parameter and return typing
- •Level-order traversal
- •Queue discipline
- •Shortest-step interpretation
Logical Thinking Concepts
- •Define invariants before coding
- •Check edge cases first (`[]`, single element, duplicates)
- •Estimate time/space before implementation
- •Apply BFS reasoning pattern
- •Apply Heap reasoning pattern
💡 Approach
- → Use min heap of size k to store k largest elements
- → Heap always contains k largest elements seen so far
- → Top of heap is kth largest element
- → Alternative: QuickSelect for average O(n) time
- → Time: O(n log k), Space: O(k)
🧭 Prerequisites
🛠️ Hints & Pitfalls
Hints
- •Use min heap of size k to store k largest elements
- •Heap always contains k largest elements seen so far
- •Top of heap is kth largest element
Common Pitfalls
- •Alternative: QuickSelect for average O(n) time
- •Time: O(n log k), Space: O(k)
🧪 Test Cases
Hidden tests on submit: 1
Test Case 1
Not run Input:
findKthLargest([3,2,1,5,6,4], 2); Expected:
5 Test Case 2
Not run Input:
findKthLargest([3,2,3,1,2,4,5,5,6], 4); Expected:
4 Test Case 3
Not run Input:
findKthLargest([1], 1); Expected:
1 📝 Code Editor
📤 Output