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

return total

--

--

--

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.

Recommended from Medium

Tiling window manager under Wayland: Sway

How Easy Is It To Set Up Progressive Web App for WooCommerce?

WooCommerce PWA Mobile App Builder

Javascript evaluator part 1: Lexing

Apache Spark: 3 Reasons Why You Should Not Use RDDs

spark-blog-2

Generating a Random String With C

ETH.LimiteD “ LAUNCHING EBET ”

Installing Xdebug on Mac OS X

⏳Java Concurrency: Java併發學習地圖

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Dhanarajappu

Dhanarajappu

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

More from Medium

Snakes and Ladders (Leetcode 909)

[LeetCode]#2089. Find Target Indices After Sorting Array

Linked List Data Structure