# Best way to find min of square of difference sub-matrices of a matrix to another matrix

235 views

suppose

``````A(n,m) =
1 2 3
4 5 6
7 8 9

and

B(p, q) =
1 1
1 1
``````

What is best method to find min of square of difference of sub-matrices of A and B e.g.

sub-matrices of A =

``````1 2    |     2 3   |    4 5    |   5 6
3 4    |     5 6   |    7 8    |   8 9
``````

Difference of first sub-matrix of A with B =

``````(1-1)  (2-1)    = |     0 1
(3-1)  (4-1)      |     2 3
``````

sum of square of elements = `0*0 + 1*1 + 2*2 + 3*3 = 14`

similar steps for other sub-matrices of A

Please suggest looking for an alternate method or algorithm which has time complexity less than `O(n*m*p*q)`

posted Jul 4, 2014
Looking for an answer?  Promote on:

I see this as a three different problems
1. one is finding the list of submatrix
And for each of sub matrix
2. Find the sum of squares of each elements
3. Find the diff of individual difference between submatrix and matrix B.

unfortunately mine is also o(n^4) so not submitting my solution. If you know something better please answer (I like to know)
Similar Questions

Given a binary matrix, find out the maximum size square sub-matrix with all 1 s, Recusively

For example, consider the below binary matrix.
(Source:- geeksforgeeks

``````   0  1  1  0  1
1  1  0  1  0
0  1  1  1  0
1  1  1  1  0
1  1  1  1  1
0  0  0  0  0
``````

The maximum square sub-matrix with all set bits is

``````1  1  1
1  1  1
1  1  1
``````

As we know it's general solution is with DP, but here i am interested in Recursive Approach

``````for(i=0;i<n;i++)