Find the Kth Smallest Sum of a Matrix With Sorted Rows — LeetCode 1439 Python Solution

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

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