kth smallest element in a sorted matrix
378. Kth Smallest Element in a Sorted Matrix
Solution modified from huahua’s post
WRONG one
The code below is WRONG
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
R, C = len(matrix), len(matrix[0])
def binary():
l, r = matrix[0][0], matrix[-1][-1]
while l<r:
m = (l+r)//2
total = 0
for row in matrix:
i = bisect.bisect_right(row, m)
total += i
if total<k:l = m+1
elif total==k:return m
else:r=m
return l
return binary()The correct one should be
Time complexity: O(nlogn*log(max -min))
Space complexity: O(1)
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
R, C = len(matrix), len(matrix[0])
def binary():
l, r = matrix[0][0], matrix[-1][-1]
while l<r:
m = (l+r)//2
total = 0
for row in matrix:
i = bisect.bisect_right(row, m)
total += i
if total<k:l = m+1
elif total>=k:r=m
return l
return binary()The reason might be, even we have k elements which are less or equal to m, the m may not exist in the matrix and hence it can not be a valid output.
For example, in the matrix
1, 4
2, 5
If we want to find the 2th element, 3 can cut the left part to have 2 elements, however, 3 is not a correct answer.
In order to make more sense for this code, let’s give another example
1, 7
2, 8
Still we need find the 2th element. Let’s do it step by step.
initially, l =1, r=8, m = 9//2 = 4
total =2 , and we set l =1, r = m = 4, new m = 5//2 = 2
total = 2, we set r =2, l is still 1. new m = 3//2 = 1
total=1 < 2, we set l = m+1 = 2
l ==r and return l.
Reference
