Completely Sorted matrix

This question 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, and all the matrix 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 larg开发者_C百科er 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.

Consider a matrix as a set of rows. In each row there are indices of the smallest and largest valid values. If you know these indices, you can calculate number of valid values in that row in O(1). (by valid I mean a value between M[i,j] and M[i0,j0].)

Now, the matrix is sorted. Lets take the lower bound: (i,j).

• If you want to find the index of smallest valid value in previous row, it has to lie on the right side of (i,j). This is because right above (i,j) there has to be invalid (too small) value.

• If you want to find the index of smallest valid value in next row, it has to lie on the left side of (i,j) (or right below it).

So you need to walk at most 2n "steps" across the matrix to find lower bound indices of every row. The same is with upper bound. So your walking is O(n), then calculating number of valid values for each row is O(n), therefore total time is O(n).

Using this algorithm it is possible to solve the median problem. Firstly note that if you calculate a solution to previous problem, you can pick a valid value at random in linear time using indices for boundary values in every row. Median can be then calculated by a bisection algorithm:

selection_find(M, i0,j0, i2,j2, K):
    # Find K-th smallest number between M(i0,j0) and M(i2,j2)
    # assumption: M(i0,j0)<M(i2,j2)
    N := number of values between M(i0,j0) and M(i2,j2)
    # assumption: k<N
    Pick at random i1,j1 so that M(i0,j0)<M(i1,j1)<M(i2,j2)
    L := number of values between M(i0,j0) and M(i1,j1)
    if L==K:
        The answer is M(i1,j1)
    if L<K:
        The answer is selection_find(M, i1,j1, i2,j2, K-L)
    if L>K:
        The answer is selection_find(M, i0,j0, i1,j1, K)

median_find(M):
    The answer is selection_find(M, 1,1, n,n, n²/2)

Each step takes O(N). There will be O(log N²)=O(2log N)=O(log N) steps (each steps should halve number of values considered). Therefore the total complexity is O(NlogN).