CODEWITHSUNDEEP
calgorithmdata-structures
Ayush Nigam
Ayush Nigam

Reputation: 461

Count no. of sub-matrices with given constraints from a matrix?

This is a question asked in one job interview. I would like to know the best optimal algorithm for getting desired results. The question is : Given you have a (n x m) matrix with some numbers in it. Now you have to count the no of matrices of size >= (2 x 2) which will have following two conditions :

I know the brute force algorithm of taking all elements of matrix 2 x 2 and greater; then counting the no. of 1's and checking 6 possible conditions of corner elements any two of them being equal. I want to know the way of dealing with these problems or any source as I could not found anything on "GeeksForGeeks" or StackOverFlow itself , in most optimized way.

Upvotes: 3

Views: 307

Answers (1)

Serge Ballesta
Serge Ballesta

Reputation: 148910

This is a hint to an optimized way.

First build a (n,m) matrix that counts the number of 1 in the (1-i, 1-j) submatrix: nm operations, nm memory

Now for each element of the matrix, search for all elements after of below that are equal

  • if on the same row you can use any row below to have a matrix with 2 corners equal
  • if on the same column, you can use any column after to have a matrix with 2 corners equal
  • if neither on the same row nor same column you have exactly one matrix with 2 corners equal
  • the difference of elements of the extreme corners of the equivalent matrix of the pre-calculated one is the number of ones in the submatrix
  • as soon as one submatrix has more than 2 ones in it all submatrix including it will also have: you can use it to short-circuit full analysis

The above is only the rough edges and there is still some work to design an algorythm, but it should be a little better than brute force for big enough matrices...

Upvotes: 3

Related Questions