Kth Smallest in Sorted Matrix

Problem

Return the k-th smallest value (1-indexed) in a matrix whose rows and columns are each sorted in ascending order.

Use a min-heap seeded with the first element of every row, then pop k times, pushing the next element from the same row after each pop. Assume k is between 1 and the total number of elements.

Hint

The heap is a merge of the sorted rows; the k-th pop is the answer.

Test cases

case 1

in: [[[1,5,9],[10,11,13],[12,13,15]],8]

expected: 13

case 2

in: [[[1,2],[3,4]],2]

expected: 2

case 3

in: [[[1]],1]

expected: 1

case 4

in: [[[-5]],1]

expected: -5

case 5

in: [[[1,3],[2,4]],3]

expected: 3

Starter codePython

def kth_smallest_matrix(matrix, k):
    # Your code here
    pass

5 test cases · run your code against them in the editor