Find the maximum element in any matrix sub-matrix

Question

I give the matrix N x M For a submatrix of length X that starts at position (a, b) , I need to find the largest element present in the submatrix.

My approach:

• 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 

Small promotion:

  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 a better solution with O (log n) complexity?

Answer 1

Algorithm approach with sparse table: - <O( N x M x log(N) x log(M)) , O(1)> .

Precompression Time - O( N x M x log(N) x log(M))
Request Time - O(1)

To understand this method, you need to know how to find RMQ using the sparse Table Algorithm for a single dimension.

We can use the 2D sparse table algorithm to find the minimum range query.

What we do in one dimension: -
we pre-process RMQ for auxiliary arrays of length 2^k using dynamic programming. We will store the array M[0, N-1][0, logN] , where M[i][j] is the index of the minimum value in the basement, starting with i . To calculate M[i][j] we must look for the minimum value in the first and second half of the interval. Obviously, the small pieces are 2^(j – 1) long, so the pseudo-code for calculating 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 the actual array in which the values ​​are stored. After that, we will pre-process these values, show how we can use them to calculate RMQ (i, j) . The idea is to select two blocks that completely cover the interval [i..j] and find the minimum between them. Let k = [log(j - i + 1)] . To calculate 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 measurements: -
In the same way, we can extend the rule above for 2 Dimension, here we pre-process RMQ for a submatrix of length 2^K, 2^L using dynamic programming and save the 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 submatrix, starting with [x , y] and having a length of 2^K, 2^L respectively. pseudo code for calculating M[x][y][k][l] : -

 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, the GetMinimum function returns the index of the minimum element from the provided elements. Now we have pre-processed, let's see how to calculate RMQ (x, y, x1, y1) . Here, [x, y] starting point of the submatrix and [x1, y1] represents the ending point of the submatrix, which means the lower right point of the submatrix. Here we must select four blocks of submatrices that completely cover [x, y, x1, y1] and find their minimum. Let k = [log(x1 - x + 1)] and l = [log(y1 - y + 1)] . To calculate RMQ (x, y, x1, y1) we can use the 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 logic above: -

 // 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

AFAIK, there can be no O (logn) approach since the matrix does not follow any order. However, if you have such an order that each row is sorted in ascending order from left to right, and each column is sorted in ascending order, you know that A [a + x] [b + x] (the lower right cell of the submatrix) is the most great element in this sub-matrix. Thus, finding the maximum takes O (1) times after sorting the matrix. However, sorting the matrix, if it is not already sorted, will cost O (NxM log {NxM})

Answer 3

Here is an example code in C ++ for the pseudocode given by @Chapta, as 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 pre-computes a two-dimensional sparse table, and then queries it in constant time. Additional information: the maximum element is stored in a sparse table, not the indexes for the maximum element.