527. 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 element (1-indexed) in the matrix. Use binary search on the value range. 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: 2nd smallest is 1.

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

Constraints

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

Asked by