Hi, this was asked to me in one of my job interviews -
M is a 2d n-by-n matrix in which every row and every column is sorted are all elements are different. I need an O(n) algorithm - Given indices i, j, i0, j0 as input, compute the number of elements of M smaller than M[i, j] and larger than M[i0, j0]. I tried various approaches for this, but couldn't figure out. Help will be greatly appreciated. The next part was to find out the median of M in O(nlogn) expected time.