Friedrich Ewald My Personal Website

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.
If we could use all the space we wanted, we could just perform an n-way merge sort on every row at once. This would work because the rows itself are sorted already. Afterwards, we would need to pick the kth element from the list and would be done. The solution I came up with uses 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]
    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.

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.