You are given an m x n matrix mat that has its rows sorted in non-decreasing order and an integer k.
You are allowed to choose exactly one element from each row to form an array.
Return the kth smallest array sum among all possible arrays.
Example 1:
Input: mat = [[1,3,11],[2,4,6]], k = 5 Output: 7 Explanation: Choosing one element from each row, the first k smallest sum are: [1,2], [1,4], [3,2], [3,4], [1,6]. Where the 5th sum is 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 Explanation: Choosing one element from each row, the first k smallest sum are: [1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]. Where the 7th sum is 9.
Constraints:
m == mat.lengthn == mat.length[i]1 <= m, n <= 401 <= mat[i][j] <= 50001 <= k <= min(200, nm)mat[i] is a non-decreasing array.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.
In this approach, we use a min-heap to efficiently retrieve the next smallest possible sum. We start by considering just the first row, then iteratively merge the results with each subsequent row.
To efficiently manage this, we maintain a min-heap where each element stores the current sum and the indices of elements used from the rows. For every extracted sum, we try to add elements from the next row to find the subsequent smallest sums. This continues until we extract the kth smallest sum.
The Python solution utilizes the built-in heapq to maintain a min-heap. We initialize the heap with the sum of the smallest elements from each row. Then, iteratively, we extract the smallest current sum and for each item in this combination, generate new sums by moving to the next element in one of the rows. If the combination of indices has not been visited, it's added to the heap.
Python
JavaScript
Time Complexity: Approximately O(k * m * log(k)), where m is the number of rows. Since we are maintaining a heap of size k, operations related to the heap (push and pop) take O(log k) time.
Space Complexity: O(k), for storing k potential sums in the heap at any point.
In this backtracking approach, we explore all possible combinations recursively, while pruning paths that cannot result in further valid sums smaller than the current best choices.
The idea is to leverage the sorted property of rows to limit the choices made by the backtracking process. We do not need to explore paths where the sum has already surpassed current known smallest sums beyond k.
Java solution uses the backtracking approach combined with a priority queue (heap) to ensure the smallest sums are always processed first. The backtracking is managed by iterating through the possible elements, while the heap manages the order efficiently.
Time Complexity: About O(k * m * log(k)) since the priority queue operations dominate the recursion depth and state exploration.
Space Complexity: O(k) for the priority queue and recursion stack.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Min-Heap Based Approach Using BFS | Time Complexity: Approximately Space Complexity: |
| Backtracking with Pruning | Time Complexity: About Space Complexity: |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Pruning | O(n^m) worst case | O(m + k) | Useful for understanding the search space or when matrix size is small and pruning removes most branches. |
| Min-Heap BFS on Sum States | O(k log k) | O(k) | Best choice when you only need the first k smallest sums and rows are sorted. |
Kth Smallest Sum Of a Matrix With Sorted Rows | LeetCode Solution | Algorithm Explanation by alGOds! • alGOds • 6,439 views views
Watch 9 more video solutions →Practice Find the Kth Smallest Sum of a Matrix With Sorted Rows with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor