#378

Kth Smallest Element in a Sorted Matrix

specialist · 640 · lc medium +30 · verified · 64.4% accepted · 10,527 likes · top 68%

Description

You have an n x n matrix in which every row and every column is sorted in non-decreasing order. Return the k-th smallest value when all elements are considered in sorted order (not the k-th distinct value).

Use a memory-efficient approach with complexity better than O(n²).

Example 1:

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8

Output: 13

Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13

Example 2:

Input: matrix = [[-5]], k = 1

Output: -5

Code

1

2

3

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int: