Find Kth Smallest Sum of a Matrix With Sorted Rows

Kth Smallest Sum in a Sorted Matrix looks scary because the number of possible sums explodes — but you never need them all. The trick is to fold the rows in one at a time and ruthlessly throw away everything that cannot be the answer.

The slow way first

The brute force is to generate every combination — one element per row — sum each one, sort them all, and take the k-th. With m rows of n values that is n^m sums. For even a modest matrix that number is astronomical, so it is hopeless.

The question to ask: do I really need every sum, or only the smallest few? We only ever want the k-th smallest. So at no point do we need to remember more than the k smallest sums built so far.

The idea: fold rows and prune to k

Process the rows one at a time. Keep a running list kept of the smallest sums you can make using the rows seen so far:

• Start with row 0 — its values are the only possible sums of a one-row pick.
• For each next row, combine every kept sum with every value in that row. That is at most k * n candidate sums.
• Sort those candidates and keep only the k smallest. Anything bigger can never end up as the k-th smallest overall, so drop it.

After folding in the last row, kept holds the k smallest full sums in order, and the answer is kept[k - 1].

The key insight: pruning back to k after every row keeps the list tiny, so the total work stays small no matter how many rows there are.

Walk through it

Step through the animation. kept starts as row 0's values, [1, 5, 9]. Folding in row 1 produces 9 candidates; we keep the 4 smallest, [11, 12, 14, 15]. Folding in row 2 produces another batch; we keep [23, 24, 24, 25]. The k-th smallest is the last kept value, 25.

Pseudocode

kept = first row's values            # possible sums using one row
for each remaining row:
    candidates = []
    for each sum s in kept:
        for each value v in row:
            candidates.append(s + v)
    kept = the k smallest of candidates   # prune
return kept[k - 1]                    # k-th smallest overall

The Python solution

import heapq
 
def kth_smallest(mat, k):
    # start with the first row's values as our sums
    kept = mat[0]
    for row in mat[1:]:
        candidates = []
        for s in kept:
            for v in row:
                candidates.append(s + v)
        # keep only the k smallest combined sums
        kept = heapq.nsmallest(k, candidates)
    return kept[k - 1]

• kept always holds the smallest sums reachable with the rows processed so far; it never grows past k.
• The double loop builds every combination of a kept sum with a value from the current row — at most k * n of them.
• heapq.nsmallest(k, candidates) is the prune step — it returns the k smallest sums and discards everything larger.
• After the last row, kept is sorted ascending, so kept[k - 1] is the k-th smallest full sum.

Complexity

We only ever hold k sums, so the space is O(k) and each row costs O(k * n) to combine plus a prune. That turns an impossible O(n^m) into a comfortable linear-in-the-rows pass.

When this pattern shows up

Practice