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.

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.

Description Hints 1 Solution Video 14:43

1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows

Q: 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.

Hard62.6% acceptance2 companies

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 k^th 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, n^m)
mat[i] is a non-decreasing array.

Asked at 2 companies

Meta Amazon

Topics

Hints open one at a time

Hint 1

Save all visited sums and corresponding indexes in a priority queue. Then, once you pop the smallest sum so far, you can quickly identify the next m candidates for smallest sum by incrementing each row index by 1.

14:43

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def kthSmallest(self, mat: List[List[int]], k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[[1,3,11],[2,4,6]]
5

Input

[[1,3,11],[2,4,6]]
9

Input

[[1,10,10],[1,4,5],[2,3,6]]
7

Your code is saved on this device.Solution