# Kth Smallest Element in a Sorted Matrix

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
Input: matrix = [[-5]], k = 1
Output: -5
• n == matrix.length
• n == 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
import heapq as h
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
arr=[]
h.heapify(arr)
n=len(matrix)

for i in range(n):
for j in range(n):
if len(arr)<k:
h.heappush(arr,-1*matrix[i][j])
else:
if(arr[0]<-1*matrix[i][j]):
h.heappush(arr,-1*matrix[i][j])
h.heappop(arr)
return arr[0]*-1
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
n=len(matrix)
low,high=matrix[0][0],matrix[n-1][n-1]
while(low<=high):
mid=(low+high)//2
cnt= self.counter(matrix,mid)
if cnt<k:
low=mid+1
else:
ans=mid
high=mid-1
return ans

def counter(self,A,k):
total=0
i,j,n=0,len(A)-1,len(A)
while(i<len(A)):
if(A[i][0]>k):
break
while(k<A[i][j]):
j-=1
total=total+j+1
i+=1

--

--

--

## More from Dhanarajappu

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.

Love podcasts or audiobooks? Learn on the go with our new app.

## Dhanarajappu

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.