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.

Accepted Answer

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(N2 * M), extra space is O(N * M).

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

Solution

Problem

Related problems