Find the Kth Smallest Sum of a Matrix With Sorted Rows
01 · Problem
You are given an m x n matrix mat in which every row is sorted in non-decreasing order, and an integer k.
Build an array by picking exactly one element from each row, and add those elements up. Consider the sums of all n^m possible picks, counted with multiplicity (different picks that produce the same sum each count separately).
Return the k-th smallest of these sums (1-indexed).
02 · Examples
mat = [[1,3,11],[2,4,6]], k = 5
7
Listing every sum in increasing order gives 3, 5, 5, 7, 7, 9, 13, 15, 17. The 5th one is 7.
mat = [[1,3,11],[2,4,6]], k = 9
17
There are exactly 3 * 3 = 9 sums, and the largest is 11 + 6 = 17.
mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
9
The smallest sums in order are 4, 5, 7, 7, 8, 8, 9, ... so the 7th smallest is 9 (for example 1 + 5 + 3).
03 · Constraints
- 01m == mat.length, n == mat[i].length
- 021 <= m, n <= 40
- 031 <= mat[i][j] <= 5000
- 041 <= k <= min(200, n^m)
- 05Each row of mat is sorted in non-decreasing order
04 · Optimal complexity
- Time
- O(m * k log k)
- Space
- O(k)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.