#1439
Find the Kth Smallest Sum of a Matrix With Sorted Rows
expert · 1130 · lc hard +32 · verified · 62.3% accepted · 1,293 likes · top 63%
Description
You are provided with an m x n matrix mat whose rows are each sorted in non-decreasing order, along with an integer k. Select exactly one element from every row to form an array; the array's score is the sum of the chosen elements. Among all possible such arrays, return the kth smallest score.
Example 1:
Input: mat = [[1,3,11],[2,4,6]], k = 5
Output: 7
Explanation: Choosing one element from each row, the first k smallest sum are:
[1,2], [1,4], [3,2], [3,4], [1,6]. Where the 5th sum is 7.
Example 2:
Input: mat = [[1,3,11],[2,4,6]], k = 9
Output: 17
Example 3:
Input: mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
Output: 9
Explanation: Choosing one element from each row, the first k smallest sum are:
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]. Where the 7th sum is 9.
Code
1
2
3