Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Kth Smallest Number in a Sorted Matrix (hard)

Problem Statement

Given an N * N matrix where each row and column is sorted in ascending order, find the Kth smallest element in the matrix.

Example 1:

Input: Matrix=[
    [2, 6, 8], 
    [3, 7, 10],
    [5, 8, 11]
  ], 
  K=5
Output: 7
Explanation: The 5th smallest number in the matrix is 7.

Constraints:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 300
  • -10<sup>9</sup> <= matrix[i][j] <= 10<sup>9</sup>
  • All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.
  • 1 <= k <= n<sup>2</sup>

.....

.....

.....

Like the course? Get enrolled and start learning!
M

Mike Xu

· 3 years ago

For the counting step in the binary search method, I recommend looking at https://leetcode.com/problems/search-a-2d-matrix-ii/

L

Learner

· 4 years ago

For the heap solution I can understand N is the number of rows,

For binary search , what is N? Is it number of rows or number of elements?

Show 7 replies
P

Pete Stenger

· 2 years ago

from heapq import heappop, heappush

class Solution:
  def countSmallerEq(self, matrix, val):
    n, m = len(matrix), len(matrix[0]) # nxm
    
    row, col = 0, m - 1
    smaller = 0

    while row < n and col >= 0:
      if matrix[row][col] <= val:
        smaller += (col + 1)
        row += 1
      elif matrix[row][col] > val:
        col -= 1
    
    return smaller
    
  def findKthSmallest(self, matrix, k):

    n, m = len(matrix), len(matrix[0])
    lo = matrix[0][0]
    hi = matrix[n-1][m-1]

    while lo <= hi:
      mid = (lo + hi) // 2
      n_smaller = self.countSmallerEq(matrix, mid)
      if n_smaller >= k:
        hi = mid - 1
      else:
        lo = mid + 1
    
    return lo