Leetcode: Kth smallest element in matrix
Given a n*n matrix, find the kth smallest element. Each row in the matrix is sorted in ascending order and independent of the other rows. Do not use O(n*n) space when solving this. One example matrix looks like this:
1 5 9
10 11 13
12 13 15
For k = 8 return 13 because 13 is the 8th smallest element.O(n) space. That is one space for a pointer to each row and column. Initially we set all rows to the first column. Then we iterate over all rows and find the smallest element in this particular position. We advance the pointer to this element by 1. Afterwards we check if we left the bounds of this array. If we did, we remove the row as a possible candidate. Finally, we take the remaining pointers and write them in a list which we sort. From that sorted list, we pick the smallest value and return it.
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
# Initialize pointer
ptr = [[i,0] for i in range(len(matrix))]
min_val = float('inf')
min_row = -1
while k > 1:
min_val = float('inf')
min_row = -1
# Find minimum row
for i, coords in enumerate(ptr):
if matrix[coords[0]][coords[1]] < min_val:
min_row = i
min_val = matrix[coords[0]][coords[1]]
# Advance minimum row by 1
ptr[min_row][1] += 1
if ptr[min_row][1] >= len(matrix):
del ptr[min_row]
k -= 1
vals = [matrix[row][col] for row, col in ptr]
vals.sort()
return vals[0]
if __name__ == '__main__':
s = Solution().kthSmallest
print(s([[1,5,9],[10,11,13],[12,13,15]], 8), 13)
print(s([[1,5,9],[10,11,13],[12,13,15]], 1), 1)
print(s([[-5]], 1), -5)
print(s([[1,2], [3,3]], 2), 2)
Runtime: 4712 ms, faster than 5.02% of Python3 online submissions for Kth Smallest Element in a Sorted Matrix. Memory Usage: 18.6 MB, less than 80.92% of Python3 online submissions for Kth Smallest Element in a Sorted Matrix.