FastPrepKth Smallest Sum from Sorted Matrix Rows
Problems/Kth Smallest Sum from Sorted Matrix Rows

Kth Smallest Sum from Sorted Matrix Rows

Amazon logoAmazon● HardFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The source defines the row-wise selection and kth-sum objective but omits duplicate-rank semantics, an interface, and bounds. The judged version counts equal sums from distinct selections separately, so the core task match is about 95%.

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) → int

Examples

Example 1

mat = [[1,3,11],[2,4,6]]k = 5return = 7

The 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 = 17

There 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 = 9

Counting 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).

More Amazon problems

  • Count Adjacent Symbol Pairs for BPEONSITE INTERVIEW · Seen Nov 2026
  • First Non-Repeating CharacterOA · ONSITE INTERVIEW · Seen Nov 2026
  • Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
See Amazon hiring insights
Saved
class Solution {
    public int kthSmallestRowSum(int[][] mat, int k) {
      // write your code here
    }
}
Checking account…