Largest submatrix with equal no of 1's and 0's

Question

Given a matrix of size mxn containing 0's and 1's only. I need to find the largest sub-matrix which has equal number of 1's and 0's in it. Brute force approach would be O(m^2*n^2) Can we do any better than this?
I tried applying dynamic programming, but couldn't find any optimal substructure to it.

I believe a similar one-dimensional version of this problem was discussed here:
Space-efficient algorithm for finding the largest balanced subarray?
which has an O(n) solution using some extra space.

Answer 1

This algorithm assumes that we search a sub-matrix with contiguous rows and columns and with the largest possible product of height and width.

Start with the following pre-processing:

A = substitute_zero_with_minus_one(InputMatrix)
B = prefix_sum_for_each_column(A)
C = prefix_sum_for_each_row(B)

Now for each pair of rows (i, j) do the folowing:

for each column k:
  d = C[k, j] - C[k, i]
  if h[d] not empty:
    if (k - h[d]) * (j - i) is greater than best result:
      update best result
  else:
    h[d] = k

Time complexity is O(N² * M), extra space is O(N * M).

Answer 2

We assume m < n, and we can have an O(M * M * N) algorithm. And if we replace all 0 by -1, we just find the largest submaxtrix whose sum is 0.

1. Get the sum of segments(i, j) in each row, we define them c1, c2, c3....,cn, we can run O(n) algorithm on it by the algorithm you referenced.
2. We should do step 1 M * M times to get the largest submaxtrix whose sum is 0, so the complexity is O(M * M * N).

Answer 3

I assume a submatrice is formed using only contiguous rows\columns of the original matrix (ie by removing first\last row or columns).

This way, a matrix can be represented as

Mat = {origin(row,col), rowCount, columnCount}

If the original matrix is of dimension M x N, then

rowCount =  M - row
columnCount = N - col
Mat = {origin(row,col), M - row, N - col}.

The variable row and col has respectively M and N possible values, which means there are O(MxN) of such matrices.

Idea of Algorithm

1. pop matrix (m, n)from queue
2. Test . If success, output matrix
3. Construct all matrices (m, n-1) and (m-1, n) and put on queue
4. go back to 1.

Now there are two points:

• When you reduce dimensions there are only 4 possible matrices (2 by removing rows, 2 by removing columns)
• You construct a sub matrix by remove either the first and last row\column. You just need remove the count for the row\column you removed, which takes O(n) or O(m) time. this is the dynamic programming step.

Which mean the complexity is O(max(M,N)MN)