Kth Smallest Sum from Sorted Matrix Rows
Problem statement
Given an integer matrix mat whose rows are sorted in nondecreasing order, choose exactly one value from each row and add the chosen values.
Return the kth smallest obtainable sum. Distinct choices occupy distinct ranks even when they produce equal sums.
Function
kthSmallestRowSum(mat: int[][], k: int) → intExamples
Example 1
mat = [[1,3,11],[2,4,6]]k = 5return = 7The ordered sums begin 3, 5, 5, 7, 7, so the fifth sum is 7.
Example 2
mat = [[1,3,11],[2,4,6]]k = 9return = 17There are nine selections, and the largest and ninth ordered sum is 11 + 6 = 17.
Example 3
mat = [[1,10,10],[1,4,5],[2,3,6]]k = 7return = 9Counting equal sums from different selections separately, the seventh ordered sum is 9.
Constraints
1 <= mat.length, mat[i].length <= 40.- All rows have the same length and are sorted in nondecreasing order.
1 <= mat[i][j] <= 5000.1 <= k <= min(200, mat[i].length^mat.length).