Find the Kth Smallest Sum of a Matrix With Sorted Rows

Find the Kth Smallest Sum of a Matrix With Sorted Rows

What is this problem about?

The Find the Kth Smallest Sum of a Matrix With Sorted Rows interview question is a high-level optimization challenge. You are given an $m imes n$ matrix where each row is sorted in non-decreasing order. You can form a sum by picking exactly one element from each row. You need to find the $k^{th}$ smallest among all possible sums.

Why is this asked in interviews?

Amazon and Meta ask the Find the Kth Smallest Sum coding problem to test a candidate's mastery of Heaps and Binary Search. It’s a "Hard" problem because the number of combinations ($n^m$) is astronomical. It evaluations whether you can use a row-by-row reduction strategy to keep the problem size manageable ($O(M \cdot K \log K)$).

Algorithmic pattern used

This problem follows the Row-by-Row Best-K pattern.

1. Initialize: Let the "best sums so far" be the elements of the first row (keeping only the top $k$).
2. Iterative Merge: For each subsequent row:

• Combine the current "best $k$ sums" with all $n$ elements of the new row to generate $k imes n$ new possible sums.
• Use a Min-Heap to efficiently find and keep only the $k$ smallest sums from this new batch.

1. Final Result: After processing all rows, the $k^{th}$ element in your "best sums" list is the answer.

Example explanation

Matrix: [[1, 10], [2, 3]], $k=3$

1. Row 1: Best sums = [1, 10].
2. Row 2: Possible sums:

• From 1: $(1+2=3, 1+3=4)$
• From 10: $(10+2=12, 10+3=13)$
• All sums: [3, 4, 12, 13].

1. Keep top $k=3$: [3, 4, 12]. Result: $3^{rd}$ smallest is 12.

Common mistakes candidates make

• Generating all sums: Trying to use recursion to find all $n^m$ sums, which will time out for even a $5 imes 5$ matrix if $k$ is large.
• Memory Management: Not limiting the size of the sum list to $k$ at each step.
• Incorrect Sorting: Forgetting that rows are already sorted, which can be leveraged to optimize the merge step using a heap.

Interview preparation tip

Master the "Merge K Sorted Lists" pattern. This problem is essentially a variation where you are merging the results of Cartesian products row by row. This is a vital Heap interview pattern for combinatorial optimization.