Kth Smallest in 2D Array | Dataford Interview Questions

An Alten Calsoft Labs data-processing component receives a matrix whose rows and columns are sorted in nondecreasing order. Given the matrix and an integer k, return the kth smallest element in the matrix, counting duplicate values as separate elements.

Implement an efficient solution without flattening and sorting the entire matrix.

Formal Specification

Input: matrix, a non-empty rectangular two-dimensional array of integers, and k, a one-based rank.
Output: The integer value whose rank is k when all matrix elements are ordered from smallest to largest.
Every adjacent pair within a row and every adjacent pair within a column is nondecreasing.

Constraints

1 <= rows, columns <= 500
1 <= k <= rows * columns
-10^9 <= matrix[i][j] <= 10^9
The matrix is rectangular
Rows and columns are sorted in nondecreasing order

Function Signature

def kth_smallest(matrix, k):

Your question is Kth Smallest in 2D Array. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem