Find the Kth Smallest Sum of a Matrix With Sorted Rows - Video Solutions

Problem Overview: You are given a matrix where each row is sorted in non-decreasing order. Pick exactly one element from every row and compute the sum. Among all possible combinations, return the k-th smallest sum.

Approach 1: Backtracking with Pruning (Exponential worst-case)

This approach explores combinations by selecting one element from each row using recursion. At every level you choose an element from the current row and accumulate the running sum. Because the rows are sorted, you can prune branches early once the partial sum already exceeds candidates in the current top k. A max-heap of size k keeps track of the smallest sums found so far. The worst-case time complexity is exponential O(n^m) where m is the number of rows and n is the number of columns, but pruning dramatically reduces the search space in practice. Space complexity is O(m + k) due to recursion depth and the heap. This method helps build intuition but struggles when the matrix dimensions grow.

Approach 2: Min-Heap BFS on Sum States (Optimal for k queries)

This approach treats the problem like exploring the smallest sums in sorted order using a min-heap. Start with the smallest possible sum by picking the first element from every row. Represent a state by the current index chosen in each row. Push the initial state into a min-heap keyed by the sum. Each time you pop the smallest sum, generate neighbors by incrementing one row index while keeping others fixed. Because rows are sorted, increasing an index guarantees the new sum is larger, preserving heap ordering. A visited set prevents duplicate states. The process continues until the k-th sum is popped. Time complexity is roughly O(k log k) heap operations, and space complexity is O(k) for the heap and visited states.

The algorithm relies heavily on a heap (priority queue) to always expand the next smallest candidate. The monotonic row ordering lets you safely generate neighbors without missing smaller sums. Understanding how sorted structures interact with heaps is key for many array and matrix search problems.

Recommended for interviews: The min-heap BFS approach is what interviewers typically expect. It demonstrates you can model the problem as a best-first search and use a priority queue to generate results in sorted order. Backtracking with pruning shows understanding of the search space, but the heap-based solution proves you can optimize enumeration problems to handle large constraints.