Kth Smallest Element in a Sorted Matrix

Nitish Chandra
Aug 29, 2017 · 2 min read

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element

Solution :

Find the range of the matrix the lowest element and the highest element the lowest element is the top left corner and the highest is the bottom right corner

Now do binary search on this If the number of element smaller than or equal to mid is greater than k then that means k the element would lie in range low — mid . Despite mid clearly has more than k numbers less than or equal to k. I would still do high = mid rather than high = mid -1 remember this is because we will not be writing condition for if the number of elments less than or equal to mid is equal to k.This is because even if mid is in the correct position element wise . It does not necessarily mean that mean is in the matrix.Otherwise if the number of elements is less than k then clearly low = mid +1

Note that low — high may not lie in the matrix they are just numbers in the range. So say we arrive at a element which is not in the matrix but which is in right position. then we check in the range low — high .Because there exits a number smaller than high which lies in the matrix with correct number of elements less than or equal to it. so our search will stop at it. Note that we do not have to worry about equal numbers. We just have to be consistent. if we are not counting equal numbers in the binary search we should not count it in any iterations .If we are counting we should count at every iterations.Eventually the number of elements less than or equal to k will be the same for all equal numbers and our search will stabilize at the required point that at low

)

Nitish Chandra

Written by

Software Engineer

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade