HardNo. 1439
Find the Kth Smallest Sum of a Matrix With Sorted Rows — LeetCode 1439 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Array, Binary Search, Matrix, Heap (Priority Queue)
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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.
Example
- 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:
Python solution
class Solution:
def kthSmallest(self, mat: List[List[int]], k: int) -> int:
pre = [0]
for cur in mat:
pre = sorted(a + b for a in pre for b in cur[:k])[:k]
return pre[-1]Complexity
- Time
- O(log n) or O(n log n)
- Space · auxiliary
- O(1)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0378 | Kth Smallest Element in a Sorted Matrix | Medium |
| 0778 | Swim in Rising Water | Hard |
| 1337 | The K Weakest Rows in a Matrix | Easy |
| 1631 | Path With Minimum Effort | Medium |
| 2812 | Find the Safest Path in a Grid | Medium |
| 0074 | Search a 2D Matrix | Medium |
Frequently asked questions
- How hard is LeetCode 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows?
LeetCode 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows is rated Hard on LeetCode.
- What topics does LeetCode 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows cover?
LeetCode 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows is tagged Array, Binary Search, Matrix and Heap (Priority Queue) on LeetCode.