# Check whether row or column swaps produce maximum size binary sub-matrix with all 1s

Given a binary matrix, the task is to find whether row swaps or column swaps give maximum size sub-matrix with all 1’s. In a row swap, we are allowed to swap any two rows. In a column swap we are allowed to swap any two columns. Output “Row Swap” or “Column Swap” and the maximum size.

Examples:

```Input : 1 1 1
1 0 1
Output : Column Swap
4
By swapping column 1 and column 2(0-based indexing),
index (0, 0) to (1, 1) makes the largest binary
sub-matrix.

Input : 0 0 0
1 1 0
1 1 0
0 0 0
1 1 0
Output : Row Swap
6

Input : 1 1 0
0 0 0
0 0 0
1 1 0
1 1 0
0 0 0
1 1 0
Output : Row Swap
8
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The idea is to find both row swap and column swap maximum size binary submatrix and compare.

To find the maximum sized binary sub-matrix with row swaps allowed, make a 2-D array, say dp[i][j]. Each value of dp[i][j] contains the number of consecutive 1s on right side of (i,j) in i-th row. Now, store each column in the 1-D temporary array one by one, say b[] and sort, and find maximum b[i] * (n – i), since b[i] is indicating the sub-matrix width and (n – i) is sub-matrix height.

Similarly, to find the maximum size binary sub-matrix with column swap allowed, find dp[i][j], where each value contains the number of consecutive 1 below the (i, j) in j-th column. Similarly, store each row in the 1-D temporary array one by one, say b[] and sort. Find maximum b[i] * (m – i), since b[i] is indicating the submatrix height and (n – i) is submatrix width.

Below is the implementation of this approach:

## C++

 `// C++ program to find maximum binary sub-matrix ` `// with row swaps and column swaps. ` `#include ` `#define R 5 ` `#define C 3 ` `using` `namespace` `std; ` ` `  `// Precompute the number of consecutive 1 below the ` `// (i, j) in j-th column and the number of consecutive 1s ` `// on right side of (i, j) in i-th row. ` `void` `precompute(``int` `mat[R][C], ``int` `ryt[][C + 2], ` `                               ``int` `dwn[R + 2][C + 2]) ` `{ ` `    ``// Travesing the 2d matrix from top-right. ` `    ``for` `(``int` `j=C-1; j>=0; j--) ` `    ``{ ` `        ``for` `(``int` `i=0; i= 0; i--) ` `    ``{ ` `        ``for` `(``int` `j = 0; j < C; ++j) ` `        ``{ ` `            ``// If (i,j) contain 0, do nothing ` `            ``if` `(mat[i][j] == 0) ` `                ``dwn[i][j] = 0; ` ` `  `            ``// Counting consecutive 1 down to (i,j). ` `            ``else` `                ``dwn[i][j] = dwn[i + 1][j] + 1; ` `        ``} ` `    ``} ` `} ` ` `  `// Return maximum size submatrix with row swap allowed. ` `int` `solveRowSwap(``int` `ryt[R + 2][C + 2]) ` `{ ` `    ``int` `b[R] = { 0 }, ans = 0; ` ` `  `    ``for` `(``int` `j=0; j cswap)? (cout << ````"Row Swap "``` `<< rswap << endl): ` `                     ``(cout << ````"Column Swap "``` `<< cswap << endl); ` `} ` ` `  `// Driven Program ` `int` `main() ` `{ ` `    ``int` `mat[R][C] = {{ 0, 0, 0 }, ` `                     ``{ 1, 1, 0 }, ` `                     ``{ 1, 1, 0 }, ` `                     ``{ 0, 0, 0 }, ` `                     ``{ 1, 1, 0 }}; ` ` `  `    ``findMax1s(mat); ` `    ``return` `0; ` `} `

## Java

 `import` `java.util.Arrays; ` ` `  `// Java program to find maximum binary sub-matrix ` `// with row swaps and column swaps. ` `class` `GFG { ` ` `  `    ``static` `int` `R = ``5``; ` `    ``static` `int` `C = ``3``; ` ` `  `// Precompute the number of consecutive 1 below the ` `// (i, j) in j-th column and the number of consecutive 1s ` `// on right side of (i, j) in i-th row. ` `    ``static` `void` `precompute(``int` `mat[][], ``int` `ryt[][], ` `            ``int` `dwn[][]) { ` `        ``// Travesing the 2d matrix from top-right. ` `        ``for` `(``int` `j = C - ``1``; j >= ``0``; j--) { ` `            ``for` `(``int` `i = ``0``; i < R; ++i) { ` `                ``// If (i,j) contain 0, do nothing ` `                ``if` `(mat[i][j] == ``0``) { ` `                    ``ryt[i][j] = ``0``; ` `                ``} ``// Counting consecutive 1 on right side ` `                ``else` `{ ` `                    ``ryt[i][j] = ryt[i][j + ``1``] + ``1``; ` `                ``} ` `            ``} ` `        ``} ` ` `  `        ``// Travesing the 2d matrix from bottom-left. ` `        ``for` `(``int` `i = R - ``1``; i >= ``0``; i--) { ` `            ``for` `(``int` `j = ``0``; j < C; ++j) { ` `                ``// If (i,j) contain 0, do nothing ` `                ``if` `(mat[i][j] == ``0``) { ` `                    ``dwn[i][j] = ``0``; ` `                ``} ``// Counting consecutive 1 down to (i,j). ` `                ``else` `{ ` `                    ``dwn[i][j] = dwn[i + ``1``][j] + ``1``; ` `                ``} ` `            ``} ` `        ``} ` `    ``} ` ` `  `// Return maximum size submatrix with row swap allowed. ` `    ``static` `int` `solveRowSwap(``int` `ryt[][]) { ` `        ``int` `b[] = ``new` `int``[R], ans = ``0``; ` ` `  `        ``for` `(``int` `j = ``0``; j < C; j++) { ` `            ``// Copying the column ` `            ``for` `(``int` `i = ``0``; i < R; i++) { ` `                ``b[i] = ryt[i][j]; ` `            ``} ` ` `  `            ``// Sort the copied array ` `            ``Arrays.sort(b); ` ` `  `            ``// Find maximum submatrix size. ` `            ``for` `(``int` `i = ``0``; i < R; ++i) { ` `                ``ans = Math.max(ans, b[i] * (R - i)); ` `            ``} ` `        ``} ` ` `  `        ``return` `ans; ` `    ``} ` ` `  `// Return maximum size submatrix with column ` `// swap allowed. ` `    ``static` `int` `solveColumnSwap(``int` `dwn[][]) { ` `        ``int` `b[] = ``new` `int``[C], ans = ``0``; ` ` `  `        ``for` `(``int` `i = ``0``; i < R; ++i) { ` `            ``// Copying the row. ` `            ``for` `(``int` `j = ``0``; j < C; ++j) { ` `                ``b[j] = dwn[i][j]; ` `            ``} ` ` `  `            ``// Sort the copied array ` `            ``Arrays.sort(b); ` ` `  `            ``// Find maximum submatrix size. ` `            ``for` `(``int` `k = ``0``; k < C; ++k) { ` `                ``ans = Math.max(ans, b[k] * (C - k)); ` `            ``} ` `        ``} ` ` `  `        ``return` `ans; ` `    ``} ` ` `  `    ``static` `void` `findMax1s(``int` `mat[][]) { ` `        ``int` `ryt[][] = ``new` `int``[R + ``2``][C + ``2``], dwn[][] = ``new` `int``[R + ``2``][C + ``2``]; ` ` `  `        ``precompute(mat, ryt, dwn); ` ` `  `        ``// Solving for row swap and column swap ` `        ``int` `rswap = solveRowSwap(ryt); ` `        ``int` `cswap = solveColumnSwap(dwn); ` ` `  `        ``// Comparing both. ` `        ``if` `(rswap > cswap) { ` `            ``System.out.println(````"Row Swap "``` `+ rswap); ` `        ``} ``else` `{ ` `            ``System.out.println(````"Column Swap "``` `+ cswap); ` `        ``} ` `    ``} ` ` `  `// Driven Program  ` `    ``public` `static` `void` `main(String[] args) { ` `        ``int` `mat[][] = {{``0``, ``0``, ``0``}, ` `        ``{``1``, ``1``, ``0``}, ` `        ``{``1``, ``1``, ``0``}, ` `        ``{``0``, ``0``, ``0``}, ` `        ``{``1``, ``1``, ``0``}}; ` ` `  `        ``findMax1s(mat); ` `    ``} ` `} ` ` `  `/* This Java code is contributed by PrinciRaj1992*/`

## C#

 `  `  `// C# program to find maximum binary sub-matrix ` `// with row swaps and column swaps. ` `using` `System; ` `public` `class` `GFG { ` `  `  `    ``static` `int` `R = 5; ` `    ``static` `int` `C = 3; ` `  `  `// Precompute the number of consecutive 1 below the ` `// (i, j) in j-th column and the number of consecutive 1s ` `// on right side of (i, j) in i-th row. ` `    ``static` `void` `precompute(``int` `[,]mat, ``int` `[,]ryt, ` `            ``int` `[,]dwn) { ` `        ``// Travesing the 2d matrix from top-right. ` `        ``for` `(``int` `j = C - 1; j >= 0; j--) { ` `            ``for` `(``int` `i = 0; i < R; ++i) { ` `                ``// If (i,j) contain 0, do nothing ` `                ``if` `(mat[i,j] == 0) { ` `                    ``ryt[i,j] = 0; ` `                ``} ``// Counting consecutive 1 on right side ` `                ``else` `{ ` `                    ``ryt[i,j] = ryt[i,j + 1] + 1; ` `                ``} ` `            ``} ` `        ``} ` `  `  `        ``// Travesing the 2d matrix from bottom-left. ` `        ``for` `(``int` `i = R - 1; i >= 0; i--) { ` `            ``for` `(``int` `j = 0; j < C; ++j) { ` `                ``// If (i,j) contain 0, do nothing ` `                ``if` `(mat[i,j] == 0) { ` `                    ``dwn[i,j] = 0; ` `                ``} ``// Counting consecutive 1 down to (i,j). ` `                ``else` `{ ` `                    ``dwn[i,j] = dwn[i + 1,j] + 1; ` `                ``} ` `            ``} ` `        ``} ` `    ``} ` `  `  `// Return maximum size submatrix with row swap allowed. ` `    ``static` `int` `solveRowSwap(``int` `[,]ryt) { ` `        ``int` `[]b = ``new` `int``[R]; ``int` `ans = 0; ` `  `  `        ``for` `(``int` `j = 0; j < C; j++) { ` `            ``// Copying the column ` `            ``for` `(``int` `i = 0; i < R; i++) { ` `                ``b[i] = ryt[i,j]; ` `            ``} ` `  `  `            ``// Sort the copied array ` `            ``Array.Sort(b); ` `  `  `            ``// Find maximum submatrix size. ` `            ``for` `(``int` `i = 0; i < R; ++i) { ` `                ``ans = Math.Max(ans, b[i] * (R - i)); ` `            ``} ` `        ``} ` `  `  `        ``return` `ans; ` `    ``} ` `  `  `// Return maximum size submatrix with column ` `// swap allowed. ` `    ``static` `int` `solveColumnSwap(``int` `[,]dwn) { ` `        ``int` `[]b = ``new` `int``[C];``int` `ans = 0; ` `  `  `        ``for` `(``int` `i = 0; i < R; ++i) { ` `            ``// Copying the row. ` `            ``for` `(``int` `j = 0; j < C; ++j) { ` `                ``b[j] = dwn[i,j]; ` `            ``} ` `  `  `            ``// Sort the copied array ` `            ``Array.Sort(b); ` `  `  `            ``// Find maximum submatrix size. ` `            ``for` `(``int` `k = 0; k < C; ++k) { ` `                ``ans = Math.Max(ans, b[k] * (C - k)); ` `            ``} ` `        ``} ` `  `  `        ``return` `ans; ` `    ``} ` `  `  `    ``static` `void` `findMax1s(``int` `[,]mat) { ` `        ``int` `[,]ryt = ``new` `int``[R + 2,C + 2]; ` `        ``int` `[,]dwn = ``new` `int``[R + 2,C + 2]; ` `  `  `        ``precompute(mat, ryt, dwn); ` `  `  `        ``// Solving for row swap and column swap ` `        ``int` `rswap = solveRowSwap(ryt); ` `        ``int` `cswap = solveColumnSwap(dwn); ` `  `  `        ``// Comparing both. ` `        ``if` `(rswap > cswap) { ` `            ``Console.WriteLine(````"Row Swap "``` `+ rswap); ` `        ``} ``else` `{ ` `            ``Console.WriteLine(````"Column Swap "``` `+ cswap); ` `        ``} ` `    ``} ` `  `  `// Driven Program  ` `    ``public` `static` `void` `Main() { ` `        ``int` `[,]mat = {{0, 0, 0}, ` `        ``{1, 1, 0}, ` `        ``{1, 1, 0}, ` `        ``{0, 0, 0}, ` `        ``{1, 1, 0}}; ` `  `  `        ``findMax1s(mat); ` `    ``} ` `} ` `  `  `/* This C# code is contributed by PrinciRaj1992*/`

Output:

```Row Swap
6
```