Approach Summary
Min-heap seeded with (nums1[0], nums2[j]) for all j. On each pop, push (nums1[i+1], nums2[j]) if valid. Extract k pairs.
How to Recognize This Pattern
- "K pairs with smallest sums from two sorted arrays"
- Min-heap with lazy expansion along one dimension
Complexity Analysis
Time Complexity
O(k log k)
Space Complexity
O(k)
Tags
Array Heap