arraysalgorithm2drmqcartesian-tree

RMQ on static 2D array in constant time

The input is an array (n*m 1<n,m< 1000). I have to find the maximum element in every sub-matrice of size( a*b ).

I was trying to do this by iterating x over n-a+1 and y over m-j+1.

Please explain a solution that will answer a query in O(nm) time or in O(1) time by pre-computation. Also, the input array is static.

Note: although I've tried sparse table, it might not have been correct, so feel free to post a solution with it.

I'm a Java coder, so an implementation in Java or c/c++ would be great.

Also this is not a duplicate as I have searched a lot about it without finding anything suitable.

Solution

  • Number of possibilities:

    (From Number of submatrix of size AxB in a matrix of size MxN)
    In a matrix of size (m*n), there are (n-A+1)*(m-B+1) different matrices of size (A*B).
    So the total number of possible input for your function is sum((n-A+1)*(m-B+1)) where A=1..n and B=1..m.

    EDIT: This is getting so huge when m=1000.

    O(m^2n^2) is O(1000^4)... 1 trillion ... this won't fit in my small computer's memory :)

    Structure:

    I propose you build an hashmap that you simply index with the boundaries of your matrix:
    A string built from a=M(i,j), b=M(k,l) where 0< i < k <(n+1) and 0< j < l <(m+1)

    Pre-computation:

    This is O(n^4), but assuming its pre-computational, there's no point, it just make your program bigger and bigger when storing aHashMap.

    Good to know

    Such problem also seem to be widely addressed at http://cs.stackexchange.com ; e.g. this or that... so this SE could be of interest to the OP.

    Implementation of this naive approach:

    With 99 x 95 it already gives millions of possibilities to pre-compute, taking about 3Go RAM!

    $ ./p1
 enter number of rows:99
 enter number of cols:95
pre-computing...
hashmap ready with 22572000 entries.

    matrix.h

    #ifndef myMatrix_JCHO
#define myMatrix_JCHO

typedef unsigned int u_it;

class Matrix
{
public:
    Matrix(u_it _n, u_it _m);
    Matrix(const Matrix& matr);
    Matrix& operator=(const Matrix& matr);
    ~Matrix();

    u_it getNumRows() ;
    u_it getNumCols() ;

    int getC(u_it i, u_it j);
    void setC(u_it i, u_it j, int v);
    void printMatrix();
    int maxSub(u_it a_i, u_it a_j, u_it b_k, u_it b_l);

private:
    u_it n, m;
    int **pC;

};

#endif

    matrix.cpp

    #include <iostream>
#include <string>
#include <sstream>

#include "matrix.h"

Matrix::Matrix(u_it _n, u_it _m) {
    n=_n;
    m=_m;
    int k=0;
    pC = new int*[n];
    for (u_it i=0; i<n; ++i){
       pC[i]=new int[m];
       for(u_it j=0; j<m; ++j){
         pC[i][j]=++k;
       }
    }
}
Matrix::~Matrix(){
    for (u_it i=0; i<n; ++i){
        delete [] pC[i];
    }
    delete [] pC;
    std::cout << "matrix destroyed\n";
}
u_it Matrix::getNumRows() {
    return n;
}
u_it Matrix::getNumCols() {
    return m;
}
int Matrix::getC(u_it i, u_it j){
    return pC[i][j];
}
void Matrix::setC(u_it i, u_it j, int v){
    pC[i][j]=v;
}
void Matrix::printMatrix(){
    for (u_it i=0; i<n; ++i){
      std::cout << "row " <<i<<" [ ";
      for(u_it j=0; j<m; ++j){
        std::cout << pC[i][j] << '\t';
      }
      std::cout << "]\n";
    }
}

// Return max of submatrix a(i,j); b(k,l)
int Matrix::maxSub(u_it a_i, u_it a_j, u_it b_k, u_it b_l) {
   int res = -100000;
   if (a_i<=b_k && a_j<=b_l && b_k<n && b_l<m) {
     for (u_it i=a_i; i<=b_k; ++i){
       for(u_it j=a_j; j<=b_l; ++j){
         res= (pC[i][j]>res)? pC[i][j] : res;
       }
     }
   } else {
     std::cout << "invalid arguments: out of bounds\n";
     return -100000;
   }

   return res;
}

    main.cpp

    #include <iostream>
#include <string>
#include <sstream>
#include <map>
#include <cassert>

#include "matrix.h"

std::string hashKey(u_it a_i, u_it a_j, u_it b_k, u_it b_l) {
    std::stringstream ss;
    ss << "max(a[" << a_i << "," << a_j << "],b[" << b_k << "," << b_l << "]";
    return ss.str();
}

int main() {
    u_it n_rows, n_cols;
    std::cout << " enter number of rows:";
    std::cin >> n_rows;
    std::cout << " enter number of cols:";
    std::cin >> n_cols;
    std::cout << " pre-computing...\n";

    std::map<std::string, int> myHMap;
    Matrix * mat=new Matrix(n_rows,n_cols);
    //mat->printMatrix();
    // "PRE" computation
    for (u_it i=0; i<n_rows; ++i) {
      for (u_it j=0; j<n_cols; ++j) {
        for (u_it k=i; k<n_rows; ++k) {
          for (u_it l=j; l<n_cols; ++l) {
            //std::cout <<"max(a["<<i<<","<<j<<"],b["<<k<<","<<l<<"]"<< mat->maxSub(i, j, k, l) <<'\n';
            //std::cout << mat->hashKey(i, j, k ,l) <<" -> " <<  mat->maxSub(i, j, k, l)  <<'\n';
            myHMap[hashKey(i, j, k ,l)] = mat->maxSub(i, j, k, l);
          }
        }
      }
    }
    std::cout << " hashmap ready with "<<  myHMap.size() <<" entries.\n";
    // call to values
    u_it cw_i, cw_j, cw_k, cw_l;
    cw_i=0;
    std::string hKey;
    while (cw_i < n_rows+1) {
      std::cout << " enter i,:";
      std::cin >> cw_i;
      std::cout << " enter j,:";
      std::cin >> cw_j;
      std::cout << " enter k,:";
      std::cin >> cw_k;
      std::cout << " enter l:";
      std::cin >> cw_l;
      hKey = hashKey(cw_i, cw_j, cw_k, cw_l);
      std::map<std::string, int>::iterator i = myHMap.find(hKey);
      assert(i != myHMap.end());
      std::cout << i->first <<" -> " <<  i->second  <<'\n';
    }
}

    make

    g++ -std=c++0x  -std=c++0x -Wall -c -g matrix.cpp
g++ -std=c++0x  -std=c++0x -Wall -c -g main.cpp
g++ -std=c++0x  -std=c++0x -Wall -g matrix.o main.o -o p1