Maximize the binary matrix by flipping submatrix once
Given a binary matrix of R rows and C columns. We are allowed to flip to any size of sub matrix. Flipping means changing 1 to 0 and 0 to 1. The task is to maximize the number of 1s in the matrix. Output the maximum number of 1s.
Examples:
Input : R = 3, C =3 mat[][] = { 0, 0, 1, 0, 0, 1, 1, 0, 1 } Output : 8 Flip 0 0 1 0 0 1 1 0 1 to get 1 1 1 1 1 1 0 1 1 Input : R = 2, C = 3 mat[][] = { 0, 0, 0, 0, 0, 0 } Output : 6
Create a matrix ones[][] of R rows and C columns, which precomputes the number of ones in the submatrix from (0, 0) to (i, j) by
// Common elements in ones[i-1][j] and // ones[i][j-1] are ones[i-1][j-1] ones[i][j] = ones[i-1][j] + ones[i][j-1] - ones[i-1][j-1] + (mat[i][j] == 1)
Since, we are allowed to flip sub matrix only once. We iterate over all possible submatrix of all possible sizes for each cell (i, j) to (i + k – 1, i + k – 1). We calculate the total number of ones after the digits are filliped in the chosen submatrix.
Total number of ones in the final matrix after flipping submatrix (i, j) to (i + k – 1) will be Ones in the whole matrix – Ones in the chosen submatrix + Zeroes in the chosen sub matrix. That comes out to be :-
ones[R][C] - cal(i, j, i + k-1, j + k - 1) + k*k - cal(i, j, i + k - 1, j + k - 1) where cal(a, b, c, d) denotes the number of ones in square submatrix of length c - a. Now cal(x1, y1, x2, y2) can be define by: ones[x2][y2] - ones[x2][y1 - 1] - ones[x1 - 1][y2] + ones[x1 - 1][y1 - 1].
Below is the implementation of this approach:
C++
Java
Python3
C#
PHP
Javascript
8
Time Complexity: O(R*C*min(R, C))
Auxiliary Space: O(R*C) because extra space for array ones is being used