957. Kth Smallest Element in a Sorted Matrix

Given an n x n matrix whose rows and columns are each sorted in ascending order, return the k-th smallest element in the matrix (in overall sorted order, counting duplicates). The input is JSON {matrix, k}.

Input: JSON {matrix, k}.

Output: Integer — the k-th smallest element.

Examples

Input: {"matrix":[[1,5,9],[10,11,13],[12,13,15]],"k":8}
Output: 13
Explanation: 8th smallest is 13.

Input: {"matrix":[[1,2],[1,3]],"k":2}
Output: 1
Explanation: Second smallest is 1.

Input: {"matrix":[[5]],"k":1}
Output: 5
Explanation: Single element.

Constraints

• 1<=n<=300
• 1<=k<=n*n

Asked by