LeetCodeKth Smallest Element in a Sorted Matrix
Binary Search
Asked at 11 companies
1 recent
- Amazon
- X
- PhonePe
- Meta
- Oracle
- TikTok
- Apple
- Microsoft
- Goldman Sachs
+1 moreShow fewer
- Bloomberg
Community-reported · source · updated 2026-10-08. ● asked in the last 6 months.
Go step by step: try it yourself before the video and the visual. Progress saves on this device.
0 / 130 pointsSolved (Medium) 0/40Reviews 0/50Mastered 0/25Practice steps 0/15
Step 1
Know these before you start
Practise each one here, or tick what you already know
Concept videoBuilds on: Two pointers from opposite ends · When sorting first unlocks the pattern
Step 2
Try it on paper
5–10 minutes, no code yet
In the wild · git bisect: To find the commit that broke a build, git halves the range of commits on every test, so even 1,000 commits take about 10 checks.
About this problem
Cut a sorted search space in half each step. Also used on answer ranges, not only arrays.
Read the full statement and examples on LeetCode, try it for 20–30 minutes, then come back for the walkthrough.
Examples
Full statement on LeetCode ↗Example 1
- Input
- matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]]k = 8
- Output
- 13
Example 2
1×1 grid- Input
- matrix = [[-5]]k = 1
- Output
- -5
Example 3
- Input
- matrix = [[1, 2], [1, 3]]k = 2
- Output
- 1
Code it here
Tab indents · ⌘/Ctrl+Enter runs · Esc leaves the editor
Step 6
Get it accepted
All test cases pass
Step 7
Review it so it sticks
Re-solve from memory after
The step that matters most: without reviews most of a solved problem fades within weeks. Three short re-solves, each just as you start to forget, are what make it yours.
Your notes
Three lines in your own words. They come back with this problem's reviews, so you can check yourself after recalling the solution.
Solve it yourself before you look
Reading the solution first feels like progress, but it makes the next similar problem — and the interview version — much harder, because you skipped the part where you figure it out. Give it an honest 20–30 minutes. Stuck? Re-read the pattern, watch the concept video, or try the brute force first.
Hidden: optimal solution
Solution code
Optimal solutionon the value, not the position. For a guess x, count the entries ≤ x by walking from the bottom-left corner (up when too big, right when small enough). The smallest x with at least k entries is the answer.
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
n = len(matrix)
def count_at_most(x: int) -> int:
count, row, col = 0, n - 1, 0
while row >= 0 and col < n:
if matrix[row][col] <= x:
count += row + 1 # this whole column part is <= x
col += 1
else:
row -= 1
return count
lo, hi = matrix[0][0], matrix[-1][-1]
while lo < hi:
mid = (lo + hi) // 2
if count_at_most(mid) >= k:
hi = mid
else:
lo = mid + 1
return loReference solution, tested in Python, Java and C++.
Other ways to solve it
- Thought of another approach (slower, or cleverer)? Code it here: the same tests check any approach.
- Community solutions on LeetCode ↗ for many more versions, in many languages. Read them after you've solved it.