CareerCup

This problem lends its self well to dynamic programming solution.

Note:
1.) Notice that the 3x3 solution rooted at A(i,j) is the same as the 2x2 solution with one more row and column added to the ends.
2.) Only valid solutions exist for even matrix.

javaish code:

findEqualSquare(int[][] A) {
    s = max(A.n, A.m)
    List<SquareMatrixStruct> answer
    answer.addAll(s, A)
    return answer
}

findEqualSquare(int s, int[][] A) {
    totalSize = s^2
    List<SquareMatrixStruct> answer = new SquareMatrixStruct[]
    for(i=0; i < n - s - 1; i++){
        for(j=0; j < n - s - 2; j++){
            Integer a = previousValues(i,j) // assume static HashMap 
             //where key is two int's, and value is Integer
            int b = 0;
            if(a==null){
                if(s == 1) {
                    a = A(i,j)
                }
                else {
                    findEqualSquare(s - 1,A)
                    a = previousValues(i,j)
                }
            }
            col=j + s
            row=i + s
            for(k=i; k < i + s; k++){
                b+=A(k,col)
            }
            for(p=j; p < j + s; p++){
                b+=A(row,p)
            }
            previousValue.put(i,j,s,b)
            if(s % 2 == 1 && b == totalSize / 2){
                answer.add(new SquareMatrixStruct(i,j,s))
            }
        }
    }
    return answer;
}

For notation sake we declare that n > m; if this is not true, switch notion of n and m to make it true.

Each operation should do no more additional work than 2(n-1)+1
That means that this takes O(n*((2n-1)+1)*m) work. This means that the operation works in O(n^2*m) time. Space is O(n*m) if we reuse (i,j) positions (This should be fine since we are preceding in a stepped fashion, first doing all s=1, then s= 2, ...).

I do not know of a better time algo. If you have one please share.

Disclaimer, uncompiled pseudocode

Does this problem have an optimal substructure property? Will "some" of the resulting solution's sub-matrix be also an optimal submatrix with equal 0's and 1's?

divide & impera

solve(A):
if A not a solution
then
  solve(A[1..m][0..n])
  solve(A[0..m][1..n])
  solve(A[0..m-1][0..n])
  solve(A[0..m][0..n-1])
else return A

begin with solve(A[0..m][0..n])


Speedups:
1. keep two LUT with number of ones on each line and column the computation is simpler o(1) for the number of 1 and 0 on every submatrix
2. in case that the size of the matrix is even skip computation and go directly to the next

replace all the 0's by -1's. take an auxiliary matrix of the same dimension (m X n). compute it's [i, j]-th entry as B[i,j] = A[i-1, j]+A[i, j-1]-A[i-1, j-1], where A is the transformed( all 0's replaced by -1's) original matrix and B our new aux matrix. the final part is to traverse B and find tuples (i, j) such that B[i, j] = 0 and compute the maximum i*j from those tuples. this can be done in O(m X n). lastly, convert all the -1's in A to 0's.

for 1 dimension array this problem can be solved with complexity O(m), (www(dot)geeksforgeeks(dot)org/archives/20586) m being the length of each row. if we make nc2 combination of rows and sum them up and apply the same algorithm as for 1D row. Hence Complexity O(n^2*m).