Kth Smallest Element in a Sorted Matrix

Given an n x n matrix where each row and each column is sorted in ascending order, return the k^th smallest value in the matrix.

The rank is based on sorted order of all n^2 entries, so duplicate numbers count multiple times.

Example:

Input:

matrix = [
  [ 1,  5,  9],
  [10, 11, 13],
  [12, 13, 15]
],
k = 8,

Output: 13

Note:

You may assume k is always valid, 1 ≤ k ≤ n^2, and 1 <= n <= 1000.

Try it yourself