492. Matrix Median

Given a matrix where each row is sorted in ascending order, return the median of all its elements. When the total number of elements is even, return the lower median (the element at 0-based index (total-1)/2 of the fully sorted values). The matrix is given as a JSON array of rows.

Input: A JSON array of sorted rows.

Output: Integer — the median value.

Examples

Input: [[1,3,5],[2,6,9],[3,6,9]]
Output: 5
Explanation: Sorted values: median is 5.

Input: [[1,3,4]]
Output: 3
Explanation: Single row median.

Input: [[5]]
Output: 5
Explanation: Single element.

Constraints

• 1<=rows,cols<=500
• row sorted ascending

Asked by