Find the Kth Smallest Sum of a Matrix With Sorted Rows

Hard
837.

Find the Kth Smallest Sum of a Matrix With Sorted Rows

Find the Kth Smallest Sum of a Matrix With Sorted Rows is a hard coding problem on arrays, binary search and matrix, asked in Amazon, Google and Uber interviews.

mat has m rows, each sorted in non-decreasing order. An array sum picks exactly one element from every row and adds them up.

Return the k-th smallest array sum among all n^m possibilities.

Example 1

Input
mat = [[1,3,11],[2,4,6]], k = 5
Output
7
Explanation
The smallest sums are 3, 5, 7, 7, 9 — the fifth is 7 (1+6 and 3+4 both give 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

Constraints

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 40
  • 1 <= mat[i][j] <= 5000
  • 1 <= k <= min(200, n^m)
  • Each row of mat is sorted in non-decreasing order.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} mat
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(mat, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Kth Smallest Sum of a Matrix With Sorted Rows Solution

Find the Kth Smallest Sum of a Matrix With Sorted Rows solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Find the Kth Smallest Sum of a Matrix With Sorted Rows is a hard coding problem on arrays, binary search and matrix, asked in Amazon, Google and Uber interviews.

Problem statement

mat has m rows, each sorted in non-decreasing order. An array sum picks exactly one element from every row and adds them up.

Return the k-th smallest array sum among all n^m possibilities.

Example 1

Input: mat = [[1,3,11],[2,4,6]], k = 5
Output: 7
Explanation: The smallest sums are 3, 5, 7, 7, 9 — the fifth is 7 (1+6 and 3+4 both give 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

Constraints

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 40
  • 1 <= mat[i][j] <= 5000
  • 1 <= k <= min(200, n^m)
  • Each row of mat is sorted in non-decreasing order.

Hints for Find the Kth Smallest Sum of a Matrix With Sorted Rows

  1. Hint 1

    n^m can be astronomically large, so the sums cannot be enumerated.

  2. Hint 2

    Merge the rows one at a time, and after each merge keep only the k smallest partial sums.

  3. Hint 3

    Anything beyond the k-th smallest partial sum can never contribute to the k-th smallest total.

How to solve Find the Kth Smallest Sum of a Matrix With Sorted Rows

Fold the rows in one by one. After absorbing a row, keep only the k smallest partial sums — the rest can never grow into one of the k smallest totals, because every remaining row only adds non-negative amounts.

Approach

  1. Start with the single partial sum 0.
  2. For each row, form every partial + element, sort, and truncate to k entries.
  3. After the last row, the answer is the k-th entry.

Why it works

If a partial sum is not among the k smallest at some stage, then at least k partial sums are no larger, and each of them extends to a total no larger than this one's best extension (the remaining rows add the same minimum to all of them). So at least k totals beat it, and it cannot be the k-th smallest. Each fold handles at most k · n candidates, bounding the whole computation.

Complexity

  • Time — O(m · k · n · log(k · n))
  • Space — O(k · n)

Pitfalls

  • Trying to enumerate all n^m combinations overflows any counter, let alone memory.
  • Truncating before sorting keeps the wrong k candidates.
  • A min-heap over (sum, indices) also works but needs a visited set to avoid re-expanding states.

Reference solution

Python

from typing import List

def kthSmallest(mat: List[List[int]], k: int) -> int:
    cur = [0]
    for row in mat:
        nxt = []
        for c in cur:
            for v in row:
                nxt.append(c + v)
        nxt.sort()
        cur = nxt[:k]
    return cur[k - 1]

Java

public static int kthSmallest(int[][] mat, int k) {
    int[] cur = new int[] { 0 };
    for (int[] row : mat) {
        int[] next = new int[cur.length * row.length];
        int p = 0;
        for (int c : cur) {
            for (int v : row) next[p++] = c + v;
        }
        Arrays.sort(next);
        int keep = Math.min(k, next.length);
        cur = Arrays.copyOf(next, keep);
    }
    return cur[k - 1];
}

C++

int kthSmallest(vector<vector<int>>& mat, int k) {
    vector<int> cur;
    cur.push_back(0);
    for (auto& row : mat) {
        vector<int> next;
        for (int c : cur) {
            for (int v : row) next.push_back(c + v);
        }
        sort(next.begin(), next.end());
        if ((int) next.size() > k) next.resize(k);
        cur = next;
    }
    return cur[k - 1];
}

JavaScript

var kthSmallest = function(mat, k) {
    var cur = [0];
    for (var r = 0; r < mat.length; r++) {
        var next = [];
        for (var i = 0; i < cur.length; i++) {
            for (var j = 0; j < mat[r].length; j++) next.push(cur[i] + mat[r][j]);
        }
        next.sort(function(a, b) { return a - b; });
        cur = next.slice(0, k);
    }
    return cur[k - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search