Find the Maximum Element in any SubMatrix of Matrix

Question

I am giving a Matrix of N x M. For a Submatrix of Length X which starts at position (a, b) i have to find the largest element present in a Submatrix.

My Approach:

1. Do as the question says: Simple 2 loops

   for(i in range(a, a + x))
   for(j in range(b, b + x)) max = max(max,A[i][j]) // N * M

A little Advance:

 1. Make a segment tree for every i in range(0, N)
 2. for i in range(a, a + x) query(b, b + x)    // N * logM

Is there any better solution having O(log n) complexity only ?

Answer 1

A Sparse Table Algorithm Approach :- <O( N x M x log(N) x log(M)) , O(1)>.

Precomputation Time - O( N x M x log(N) x log(M))
Query Time - O(1)

For understanding this method you should have knowledge of finding RMQ using sparse Table Algorithm for one dimension.

We can use 2D Sparse Table Algorithm for finding Range Minimum Query.

What we do in One Dimension:-
we preprocess RMQ for sub arrays of length 2^k using dynamic programming. We will keep an array M[0, N-1][0, logN] where M[i][j] is the index of the minimum value in the sub array starting at i. For calculating M[i][j] we must search for the minimum value in the first and second half of the interval. It’s obvious that the small pieces have 2^(j – 1) length, so the pseudo code for calculation this is:-

if (A[M[i][j-1]] < A[M[i + 2^(j-1) -1][j-1]])
    M[i][j] = M[i][j-1]
else 
    M[i][j] = M[i + 2^(j-1) -1][j-1]

Here A is actual array which stores values.Once we have these values preprocessed, let’s show how we can use them to calculate RMQ(i, j). The idea is to select two blocks that entirely cover the interval [i..j] and find the minimum between them. Let k = [log(j - i + 1)]. For computing RMQ(i, j) we can use the following formula:-

if (A[M[i][k]] <= A[M[j - 2^k + 1][k]])
    RMQ(i, j) = A[M[i][k]]
else 
    RMQ(i , j) = A[M[j - 2^k + 1][k]]

For 2 Dimension :-
Similarly We can extend above rule for 2 Dimension also , here we preprocess RMQ for sub matrix of length 2^K, 2^L using dynamic programming & keep an array M[0,N-1][0, M-1][0, logN][0, logM]. Where M[x][y][k][l] is the index of the minimum value in the sub matrix starting at [x , y] and having length 2^K, 2^L respectively. pseudo code for calculation M[x][y][k][l] is:-

M[x][y][i][j] = GetMinimum(M[x][y][i-1][j-1], M[x + (2^(i-1))][y][i-1][j-1], M[x][y+(2^(j-1))][i-1][j-1], M[x + (2^(i-1))][y+(2^(j-1))][i-1][j-1])

Here GetMinimum function will return the index of minimum element from provided elements. Now we have preprocessed, let's see how to calculate RMQ(x, y, x1, y1). Here [x, y] starting point of sub matrix and [x1, y1] represent end point of sub matrix means bottom right point of sub matrix. Here we have to select four sub matrices blocks that entirely cover [x, y, x1, y1] and find minimum of them. Let k = [log(x1 - x + 1)] & l = [log(y1 - y + 1)]. For computing RMQ(x, y, x1, y1) we can use following formula:-

RMQ(x, y, x1, y1) = GetMinimum(M[x][y][k][l], M[x1 - (2^k) + 1][y][k][l], M[x][y1 - (2^l) + 1][k][l], M[x1 - (2^k) + 1][y1 - (2^l) + 1][k][l]);

pseudo code for above logic:-

// remember Array 'M' store index of actual matrix 'P' so for comparing values in GetMinimum function compare the values of array 'P' not of array 'M' 
SparseMatrix(n , m){ // n , m is dimension of matrix.
    for i = 0 to 2^i <= n:
        for j = 0 to 2^j <= m:
            for x = 0 to x + 2^i -1 < n :
                for y = 0 to y + (2^j) -1 < m:
                    if i == 0 and j == 0:
                        M[x][y][i][j] = Pair(x , y) // store x, y
                    else if i == 0:
                        M[x][y][i][j] = GetMinimum(M[x][y][i][j-1], M[x][y+(2^(j-1))][i][j-1])
                    else if j == 0:
                        M[x][y][i][j] = GetMinimum(M[x][y][i-1][j], M[x+ (2^(i-1))][y][i-1][j])
                    else 
                        M[x][y][i][j] = GetMinimum(M[x][y][i-1][j-1], M[x + (2^(i-1))][y][i-1][j-1], M[x][y+(2^(j-1))][i-1][j-1], M[x + (2^(i-1))][y+(2^(j-1))][i-1][j-1]);
}
RMQ(x, y, x1, y1){
    k = log(x1 - x + 1)
    l = log(y1 - y + 1)
    ans = GetMinimum(M[x][y][k][l], M[x1 - (2^k) + 1][y][k][l], M[x][y1 - (2^l) + 1][k][l], M[x1 - (2^k) + 1][y1 - (2^l) + 1][k][l]);
    return P[ans->x][ans->y] // ans->x represent Row number stored in ans and similarly ans->y represent column stored in ans
}

Answer 2

Here is the sample code in c++, for the pseudo code given by @Chapta, as was requested by some user.

int M[1000][1000][10][10];
int **matrix;

void precompute_max(){
    for (int i = 0 ; (1<<i) <= n; i += 1){
        for(int j = 0 ; (1<<j) <= m ; j += 1){
            for (int x = 0 ; x + (1<<i) -1 < n; x+= 1){
                for (int y = 0 ;  y + (1<<j) -1 < m; y+= 1){
                    if (i == 0 and j == 0)
                        M[x][y][i][j] = matrix[x][y]; // store x, y
                    else if (i == 0)
                        M[x][y][i][j] = max(M[x][y][i][j-1], M[x][y+(1<<(j-1))][i][j-1]);
                    else if (j == 0)
                        M[x][y][i][j] = max(M[x][y][i-1][j], M[x+ (1<<(i-1))][y][i-1][j]);
                    else 
                        M[x][y][i][j] = max(M[x][y][i-1][j-1], M[x + (1<<(i-1))][y][i-1][j-1], M[x][y+(1<<(j-1))][i-1][j-1], M[x + (1<<(i-1))][y+(1<<(j-1))][i-1][j-1]);
                    // cout << "from i="<<x<<" j="<<y<<" of length="<<(1<<i)<<" and length="<<(1<<j) <<"max is: " << M[x][y][i][j] << endl;
                }
            }
        }
    }
}

int compute_max(int x, int y, int x1, int y1){
    int k = log2(x1 - x + 1);
    int l = log2(y1 - y + 1);
    // cout << "Value of k="<<k<<" l="<<l<<endl;
    int ans = max(M[x][y][k][l], M[x1 - (1<<k) + 1][y][k][l], M[x][y1 - (1<<l) + 1][k][l], M[x1 - (1<<k) + 1][y1 - (1<<l) + 1][k][l]);
    return ans;
}

This code first precomputes, the 2 dimensional sparse table, and then queries it in constant time. Additional info: the sparse table stores the maximum element and not the indices to the maximum element.