function countLess (Arrr,num){
var count=0;
for(var x=0;x<Arrr.length;x++){
Arr=Arrr[x];
var high=Arr.length-1;
var low=0;
while(low<=high){
var mid=Math.floor((high+low)/2);
if(num>Arr[high]){
count+=(high-low)+1;
low=high+1;
}else if(num< Arr[low]){
count+=0;
low=high+1;
}else{
if(num>=Arr[mid]){
count+=(mid-low)+1
low=mid+1;
}else{
high=mid-1;
}
}
}
}
return count;
}
function findmedian(A){
var max=Number.MAX_VALUE, min=0, med=Math.floor(1+(A.length*A[0].length)/2);
while(max-min>1){
var pivot=Math.floor((max+min)/2);
for(var i=0;i<A.length;i++){
for(var j=0;j<A[i].length;j++){
if(A[i][j]>pivot){
min=pivot;
}
if(A[i][j]<max && A[i][j]>=min){
var count=countLess(A,A[i][j]);
if(count==med){
max=A[i][j];
min=max;
}else if(count>med){
max=A[i][j];
}else{
if(A[i][j]>min&&A[i][j]<max){
min=A[i][j];
}
}
}
}
}
}
return max;
}
var Arr=[
[1, 3, 5],
[2, 6, 9],
[3, 6, 9]
];
console.log(findmedian(Arr));
This is what I came up with after a full day of rumination
There is probably a cleaner way to write this code, so I may revise it.
I had an inkling of inspiration explaining the problem here, but it didn’t fully click until late last night.
I had to visit every element of the matrix, but I didn’t have to do a lesser element count for every element.
To be the median, you would either have exactly 1+(NM)/2 elements less than or equal to you, or you’d be the smallest number in a group that has more than 1+(NM)/2 element less than or equal to you.
I can essentially filter the matrix on the fly using 1+(N*M)/2 and the counting function. Updating the range of where the median could be as I go through the matrix. You only have to do counts for elements within the range. Eventually, the range would narrow to smallest of the “greater than or equal to” group, and the largest of the “less than” group, the first of which is the median. Since I don’t really care about the lower bound, I can also update it via a binary search pivot(midpoint).
The counting function is O(Nlog(M)) but since you don’t have to count every element, the number in front becomes however long it takes to encounter the median or median-1.