This seems like the simplest and most time/space efficient solution. What am I missing?
def find_Kth_smallest(matrix, k):
n = len(matrix)
row = (k-1) % n
col = (k-1) // n
return matrix[row][col]
Yeah like if the matrix is already sorted why bother with either k-way merge or binary search? This has happened multiple times throughout this course where all the example cases follow some constraint that isn’t explicitly stated, but makes the solution to those examples much easier than the solution presented by the course.
What you’re missing, though (and what I had missed until 2 minutes ago), is that the rows and columns being sorted in ascending order doesn’t guarantee that a left to right/up to down or up to down/left to right traversal of the matrix is gonna result in a sorted array. Take this matrix, for example
[1, 5, 9],
[10, 11, 13]
[12, 13, 15]
1 Like