Kth Smallest Sum of a Matrix With Sorted Rows
Find the kth smallest sum across all row combinations using a row-by-row min-heap merge.
Kth Smallest Sum of a Matrix With Sorted Rows
Problem: Given an m × n matrix where each row is sorted in ascending order, choose one element from each row and sum them. Find the kth smallest such sum across all possible combinations.
Example:
- Input:
mat = [[1,3,11],[2,4,6]],k = 5 - Output:
7 - All sums: 1+2=3, 1+4=5, 3+2=5, 1+6=7, 3+4=7, ... The 5th smallest is 7.
Note
Instead of generating all combinations (exponential), merge rows one at a time. After merging two rows, you get a sorted list of k smallest pairwise sums — then merge that with the next row, and so on.
Brute Force
View Brute Force
Optimal — Row-by-Row Min-Heap Merge
View Optimal Solution
| Approach | Time | Space |
|---|---|---|
| All combinations | O(n^m log n^m) | O(n^m) |
| Min-Heap row merge | O(m × k log k) | O(k) |
LeetCode 1439 — Find the Kth Smallest Sum of a Matrix With Sorted Rows