Totally defeated by algorithm mock interview question

I bang my head over for over an hour and my final solution still didn’t pass all the criteria. Even after it’s been explained to me, I’m still unclear.

Can anyone do it and explain to me your process?

You have a Matrix of size N*M, every row is sorted from least to most, find the median of the matrix. You can assume the size is always odd, so there is always a median. No extra memory is allow, ie, you cannot allocate a new array, and sort that array. You are allowed to declare and assign values to variable.

Example:

[[1, 3, 5],
[2, 6, 9],
[3, 6, 9]]

median is 5

This might be of some help…

i’ve definitely looked into that already, I even understand the logic to use binary search tree count elements less than that number. I however don’t understand how they averted searching every element in the matrix.

A good implementation in javascript still eludes me. I got as far as written the functions that counts the elements less than a number, but it still is O(NNMlog(M)) and that was too inefficient.

Here is my solution. It isn’t a highly efficient, but it seems to pass the criteria required:

Loop through each array, look at index 0 (i it exists) and find the array that has the minimum value, remove that from the array, keep track of the index we are at. After we hit the median index, stop.

const arr = [
  [1, 3, 5],
  [2, 6, 9],
  [3, 6, 9]
];

const N = arr.length;
const M = arr[0].length;
const middleI = Math.floor((N * M) / 2)

let i = 0;
let min = null;
let median = null;

while (i++ <= middleI) {
  min = Infinity;
  let minArr = null;
  for (let j = 0; j < N; j++) {
    if (arr[j].length > 0 && arr[j][0] < min) {
      minArr = arr[j];
      min = arr[j][0];
    }
  }
  if (minArr) {
    median = minArr.shift();
  }
}

console.log('median', median);

Are there any more details to the question? Maybe some example matrices that show how it should be tricky? Because at first glance it seems like it should be really easy:

  • Find the minimum and maximum value in the array of arrays, and then calculate the median using those two values. And since the sub-arrays are sorted that reduces the amount of comparisons you have to make. If I’m missing something, it’s not apparent from the provided description.

The median is not the same as the mean or average.

What you proposed is the average (or mean) of 2 numbers.

The trickiest part for me has been efficiency. O(N*log(M)) is what is required to pass fully

How do you calculate the median from just the Min and the Max? Do you mean using those to set the range?

Oh, I like it. You basically keep finding the smallest element until you hit the middle of a big array you never made.

However, I think it might be inefficient because the small numbers aren’t always distributed evenly

That’s right, thanks for that correction! I’d forgotten how the median works and in that example it just happens to be the same as the average.

Actually you can’t, I’d forgotten how determining the median works.

But codyseibert’s general approach is how I would do it too. Granted, I wouldn’t have done it exactly the same way, but the approach of finding the next “minimum” value up until N*M/2, because that’s where you know the median is spatially. Or alternately you can start at the “end” and go backwards by finding the next “maximum” value, either way would work.

I think that’s a good approach. I wish I’ve thought of that;

I’d have written the code faster. it would have failed the efficiency part because it’s O(NNM) and they were looking for O(N*log(M)), but at least I’d have looked less frustrated.

However, I’d have never come up with that approach once they give the hint that I should use a binary search tree

They told you it had to be O(N*log(M))? Dang, thats rough… if you see a “log” in the O function, it is usually binary search or some type of divide and conquer.

No, they actually told me I should use a BST first, but it ended up frustrating me even more. The trick is to count how many elements are less or equal to a number or greater or equal to a number, and when you hit (N*M/2)+1, you got the median. I got that figured out when they give me the hint, but I couldn’t figure out how they avoided doing counts on all the numbers

It was not a real interview, so the interviewer had time to walk me through what they wanted in the end, but even so, I’m still pretty confused. What they walked through is very similar to the first answer in the stackexchange thread

Eh, don’t feel bad. I have read that stack overflow answer a couple times now and I still don’t understand how it works, and I’ve been a web developer for 4 years now. The most important part of interview questions like this isn’t if you get the solution correct or not, but how you walk the interview through for deriving an answer.

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.

^ in your code, this is O(N*M).

So the weird bit is that this is what finally broke through the InterviewBit’s timeout gate on their platform. I think it has to do with the count function being dependent on the outer while loop rather than the nested for loops

It’s definitely sluggish with smaller test cases, but for some reason it passes the bigger test cases. I think now that I understand what’s going on a little better, I can probably write a less clunky solution