Search for a command to run...
Use binary search on the value range and count elements to find the median
Current step
Find the median of the row-wise sorted matrix. The median requires at least 7 elements to be smaller or equal to it. The possible value range is [1, 29].
Binary Search on Value Range
1class Solution {2 upperBound(arr, x, m) {3 let low = 0, high = m - 1;4 let ans = m;5 6 while (low <= high) {7 let mid = Math.floor((low + high) / 2);8 9 if (arr[mid] > x) {10 ans = mid;11 high = mid - 1;12 } else {13 low = mid + 1;14 }15 }16 return ans;17 }18 19 countSmallEqual(matrix, n, m, x) {20 let cnt = 0;21 for (let i = 0; i < n; i++) {22 cnt += this.upperBound(matrix[i], x, m);23 }24 return cnt;25 }26 27 findMedian(matrix) {28 let n = matrix.length, m = matrix[0].length;29 let low = Infinity, high = -Infinity;30 31 for (let i = 0; i < n; i++) {32 low = Math.min(low, matrix[i][0]);33 high = Math.max(high, matrix[i][m - 1]);34 }35 36 let req = Math.floor((n * m) / 2);37 38 while (low <= high) {39 let mid = Math.floor((low + high) / 2);40 41 let smallEqual = this.countSmallEqual(matrix, n, m, mid);42 43 if (smallEqual <= req) low = mid + 1;44 else high = mid - 1;45 }46 47 return low;48 }49}