What is the main pattern for solving the 'Find the Kth Smallest Sum of a Matrix With Sorted Rows' problem?

The key pattern is binary search over the valid answer space, combined with a heap to efficiently generate and track the kth smallest sum.

How does binary search apply to this problem?

Binary search is used to narrow down the possible sum range, adjusting the bounds based on the smallest and largest possible sums in the matrix.

Why is using a heap important for this problem?

A heap allows you to track the smallest sums efficiently, ensuring you always generate the next smallest sum without having to sort all possibilities.

What are some common pitfalls when solving this problem?

Common pitfalls include failing to implement binary search correctly, not managing the heap efficiently, or confusing this problem with simpler sum problems.

How can GhostInterview assist with solving this problem?

GhostInterview provides hints on binary search and heap usage, guiding candidates through the problem-solving process and ensuring an efficient solution.

#1439

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

有序矩阵中的第 k 个最小数组和

给你一个 m * n 的矩阵 mat ，以及一个整数 k ，矩阵中的每一行都以非递减的顺序排列。你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个最小数组和。示例 1：输入： mat = [[1,3,11],[2,4,6]], k = 5 输出： 7 解释：从每…

数组二分查找堆（优先队列）矩阵

题目描述

给你一个 m * n 的矩阵 mat，以及一个整数 k ，矩阵中的每一行都以非递减的顺序排列。

你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个最小数组和。

示例 1：

输入：mat = [[1,3,11],[2,4,6]], k = 5
输出：7
解释：从每一行中选出一个元素，前 k 个和最小的数组分别是：
[1,2], [1,4], [3,2], [3,4], [1,6]。其中第 5 个的和是 7 。

示例 2：

输入：mat = [[1,3,11],[2,4,6]], k = 9
输出：17

示例 3：

输入：mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
输出：9
解释：从每一行中选出一个元素，前 k 个和最小的数组分别是：
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]。其中第 7 个的和是 9 。

示例 4：

输入：mat = [[1,1,10],[2,2,9]], k = 7
输出：12

提示：

m == mat.length
n == mat.length[i]
1 <= m, n <= 40
1 <= k <= min(200, n ^ m)
1 <= mat[i][j] <= 5000
mat[i] 是一个非递减数组

lightbulb

解题思路

方法一：逐行遍历 + 排序

根据题目描述，我们需要找出前 $m$ 行的所有可能数组中的第 $k$ 个最小数组和。

如果我们能够找出前 $m - 1$ 行的所有可能数组中的前 $k$ 个最小数组和，那么我们可以将第 $m$ 行的每个元素与前 $m - 1$ 行的前 $k$ 个最小数组和相加，将得到的所有结果排序后，取前 $k$ 个最小值，即为前 $m$ 行的所有可能数组中的前 $k$ 个最小值。

因此，我们可以定义一个数组 $pre$ ，用于存储此前遍历到的行的前 $k$ 个最小数组和，初始时 $pre$ 只有一个元素 $0$ 。

然后，我们遍历 $mat$ 的每一行 $cur$ ，将 $cur$ 中的每个元素与 $pre$ 中的每个元素相加，将得到的所有结果排序后，取前 $k$ 个最小值作为新的 $pre$ 。继续遍历下一行，直到遍历完所有行。

最后返回 $pre$ 中的第 $k$ 个数（下标 $k-1$ ）即可。

时间复杂度 $O(m \times n \times k \times \log (n \times k))$ ，空间复杂度 $O(n \times k)$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

1

2

3

4

5

6

7

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]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates understanding of binary search and heap-based approaches for solving matrix sum problems.
question_mark
The candidate effectively applies binary search over the valid sum range and uses a priority queue for efficient sum management.
question_mark
Look for a solution where the candidate avoids a brute-force approach and ensures that the algorithm works within the problem's constraints.

warning

常见陷阱

外企场景

error
Failure to implement binary search correctly, leading to excessive computation.
error
Not using the heap efficiently to track sums, causing performance issues for larger matrices.
error
Confusing the problem with typical sum problems that don't involve sorted rows or the heap structure.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider solving with larger matrices, adjusting the binary search bounds appropriately.
arrow_right_alt
Explore optimization strategies for reducing space complexity when working with very large k values.
arrow_right_alt
Test variations where some rows are empty or have more than one element to ensure robustness.

help

常见问题

外企场景

继续练习

#1337 矩阵中战斗力最弱的 K 行 #1631 最小体力消耗路径 #778 水位上升的泳池中游泳