Category: k_way_merge
-
LeetCode 378: Kth Smallest Element in a Sorted Matrix
link Sweep line With row heads in a min-heap, we can traverse the elements in sorted order using sweep line. Time: , space: .
-
LeetCode 23: Merge k Sorted Lists
link Sweep line With the list heads in a min-heap, we can traverse them in sorted order using sweep line. If we have a tuple like in the heapq, the primary key is and the secondary key is . The primary keys are compared using strictly-less-than operator. If there is a tie, the comparison is…
-
LeetCode 373: Find K Pairs with Smallest Sums
link For a pair , and . Sweep line We can group the pairs by distinct ‘s. Since a group has a fixed and nums2 is sorted, we can consider each group as a sorted list of pairs . Keeping group heads in a min-heap, we can generate the pairs in sorted order of their…
unreasonably effective 