Kth Smallest Element in a Sorted Matrix

Given an n x n matrix where each row and column is sorted in ascending order, find the kth smallest element in the sorted order. The solution should have a memory complexity better than O(n^2).

Constraints

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 300
  • -10^9 <= matrix[i][j] <= 10^9
  • All rows and columns of matrix are sorted in non-decreasing order.
  • 1 <= k <= n^2
View editorial solution
Saving… · 2 lines
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
Console

Click Run to execute sample tests.