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.
How to Think About It
Starting point: Generate every possible combination (one element per row), compute each sum, sort all sums, return the kth. That's n^m combinations — exponential and completely impractical.
The key reduction: Instead of thinking "all combinations across all rows at once", think row by row. If you had just two rows, you'd need the k smallest pairwise sums. That's a known, tractable problem.
Row-by-row merging: Process rows one at a time. Start with row 1 as your "current sums". Merge with row 2 to get the k smallest sums from all (row1, row2) pairs. Merge that result with row 3. Repeat. After m merges, you have the k smallest sums across all rows.
How to merge two sorted arrays and keep k smallest: Start at (arr1[0] + arr2[0], i=0, j=0) — the minimum possible sum. From any state (sum, i, j), the next candidates are (sum - arr1[i] + arr1[i+1], i+1, j) and (sum - arr2[j] + arr2[j+1], i, j+1). Push both, use a min-heap to always pop the smallest, and stop after k pops.
Avoiding duplicate states: The same (i, j) pair can be reached multiple ways (right then down, or down then right). Use a visited set of (i, j) pairs to skip states already enqueued.
The pattern: Structured search with a min-heap — you exploit the sorted order to expand only the most promising candidates, never generating the full space.
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