378. Kth Smallest Element in a Sorted Matrix
Problem Statement
Given an n x n
matrix
where each of the rows and columns is sorted in ascending order, return the kth
smallest element in the matrix.
Note that it is the kth
smallest element in the sorted order, not the kth
distinct element.
You must find a solution with a memory complexity better than O(n2)
.
Example 1:
Example 2:
Constraints:
n == matrix.length == matrix[i].length
1 <= n <= 300
-109 <= matrix[i][j] <= 109
All the rows and columns of
matrix
are guaranteed to be sorted in non-decreasing order.1 <= k <= n2
Intuition
Links
Video Links
Approach 1:
Approach 2:
Approach 3:
Approach 4:
Similar Problems
Last updated