Skip to main content
Talentd

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

HardArrayBinary SearchHeap (Priority Queue)Matrix10 min readAsked at: Amazon, Meta
Practice this problem

Problem Statement

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.length
  • n == mat.length[i]
  • 1 <= m, n <= 40
  • 1 <= mat[i][j] <= 5000
  • 1 <= k <= min(200, nm)
  • mat[i] is a non-decreasing array.

Approach Overview

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.

Approach 1: Min-Heap Based Approach Using BFS

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Backtracking with Pruning

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.

Code

JavaC++

Java

C++

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Min-Heap Based Approach Using BFS

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.

Backtracking with Pruning

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.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking with PruningO(n^m) worst caseO(m + k)Useful for understanding the search space or when matrix size is small and pruning removes most branches.
Min-Heap BFS on Sum StatesO(k log k)O(k)Best choice when you only need the first k smallest sums and rows are sorted.

Video Solution

Kth Smallest Sum Of a Matrix With Sorted Rows | LeetCode Solution | Algorithm Explanation by alGOds! • alGOds • 6,556 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Kth Smallest Sum of a Matrix With Sorted Rows easy or hard?
The problem is classified as Hard because it requires combining multiple concepts: heap-based search, state representation with indices, and careful duplicate handling. The challenge is recognizing that you should generate sums in sorted order rather than enumerating all combinations.
Find the Kth Smallest Sum of a Matrix With Sorted Rows Python or Java solution
Most implementations use a priority queue with a tuple storing the current sum and row indices. Python solutions typically use heapq, while Java solutions rely on PriorityQueue with a custom comparator. Both versions maintain a visited set to avoid duplicate states and stop after the k-th extraction.
How to solve Find the Kth Smallest Sum of a Matrix With Sorted Rows efficiently?
Model each combination as a state containing indices from every row and track the sum of those elements. Insert the smallest possible state into a min-heap. Repeatedly pop the smallest sum and push neighboring states where one row index is incremented. After extracting k states, the last popped sum is the answer.
What is the best approach for Find the Kth Smallest Sum of a Matrix With Sorted Rows?
The most efficient solution uses a min-heap (priority queue) to perform a best-first search over possible sums. Start with the smallest combination using the first element from each row, then expand neighbors by incrementing row indices. The heap always returns the next smallest candidate sum. This approach runs in about O(k log k) time with O(k) extra space.
What data structure is used in Find the Kth Smallest Sum of a Matrix With Sorted Rows?
The core data structure is a min-heap (priority queue). It stores candidate sums along with their row index combinations so the algorithm always processes the smallest sum next. A hash set or visited structure is also used to prevent pushing duplicate index states into the heap.
What is the time complexity of Find the Kth Smallest Sum of a Matrix With Sorted Rows?
The optimal heap-based solution runs in O(k log k) time because each step pops the smallest sum from the priority queue and pushes new candidate states. Space complexity is O(k) for the heap and visited set. A naive backtracking solution can degrade to exponential O(n^m) time where m is the number of rows.
Is Find the Kth Smallest Sum of a Matrix With Sorted Rows asked at Google, Amazon, or Meta?
This problem represents a common interview pattern involving heaps and k-th smallest element queries. Variants of the problem appear in interviews at companies like Google, Amazon, and Meta where candidates must combine sorted structures with priority queues to generate ordered results efficiently.

Ready to solve this problem?

Practice Find the Kth Smallest Sum of a Matrix With Sorted Rows with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays