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
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 <bits/stdc++.h> #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]) { // Traversing 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; } } // Traversing 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. int solveRowSwap(int ryt[R + 2][C + 2]) { int b[R] = { 0 }, 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 sort(b, b + R); // Find maximum submatrix size. for (int i = 0; i < R; ++i) ans = max(ans, b[i] * (R - i)); } return ans; } // Return maximum size submatrix with column // swap allowed. int solveColumnSwap(int dwn[R + 2][C + 2]) { int b[C] = { 0 }, 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 sort(b, b + C); // Find maximum submatrix size. for (int i = 0; i < C; ++i) ans = max(ans, b[i] * (C - i)); } return ans; } void findMax1s(int mat[R][C]) { int ryt[R + 2][C + 2], dwn[R + 2][C + 2]; memset(ryt, 0, sizeof ryt); memset(dwn, 0, sizeof dwn); precompute(mat, ryt, dwn); // Solving for row swap and column swap int rswap = solveRowSwap(ryt); int cswap = solveColumnSwap(dwn); // Comparing both. (rswap > cswap)? (cout << "Row Swap\n" << rswap << endl): (cout << "Column Swap\n" << 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[][]) { // Traversing 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; } } } // Traversing 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\n" + rswap); } else { System.out.println("Column Swap\n" + 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*/ |
Python3
# Python3 program to find maximum binary # sub-matrix with row swaps and column swaps. R, C = 5, 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. def precompute(mat, ryt, dwn): # Traversing the 2d matrix from top-right. for j in range(C - 1, -1, -1): for i in range(0, R): # 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 # Traversing the 2d matrix from bottom-left. for i in range(R - 1, -1, -1): for j in range(0, C): # 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. def solveRowSwap(ryt): b = [0] * R ans = 0 for j in range(0, C): # Copying the column for i in range(0, R): b[i] = ryt[i][j] # Sort the copied array b.sort() # Find maximum submatrix size. for i in range(0, R): ans = max(ans, b[i] * (R - i)) return ans # Return maximum size submatrix # with column swap allowed. def solveColumnSwap(dwn): b = [0] * C ans = 0 for i in range(0, R): # Copying the row. for j in range(0, C): b[j] = dwn[i][j] # Sort the copied array b.sort() # Find maximum submatrix size. for i in range(0, C): ans = max(ans, b[i] * (C - i)) return ans def findMax1s(mat): ryt = [[0 for i in range(C + 2)] for j in range(R + 2)] dwn = [[0 for i in range(C + 2)] for j in range(R + 2)] precompute(mat, ryt, dwn) # Solving for row swap and column swap rswap = solveRowSwap(ryt) cswap = solveColumnSwap(dwn) # Comparing both. if rswap > cswap: print("Row Swap\n", rswap) else: print("Column Swap\n", cswap) # Driver Code if __name__ == "__main__": mat = [[0, 0, 0], [1, 1, 0], [1, 1, 0], [0, 0, 0], [1, 1, 0]] findMax1s(mat) # This code is contributed by Rituraj Jain |
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) { // Traversing 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; } } } // Traversing 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\n" + rswap); } else { Console.WriteLine("Column Swap\n" + 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*/ |
Javascript
// JS program to find maximum binary sub-matrix // with row swaps and column swaps. let R = 5 let 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. function precompute( mat, ryt, dwn) { // Traversing the 2d matrix from top-right. for (var j=C-1; j>=0; j--) { for (var 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; } } // Traversing the 2d matrix from bottom-left. for (var i = R - 1; i >= 0; i--) { for (var 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. function solveRowSwap( ryt) { let b = new Array(R).fill(0) let ans = 0; for (var j=0; j<C; j++) { // Copying the column for (var i=0; i<R; i++) b[i] = ryt[i][j]; // Sort the copied array b.sort(function(x, y) { return x - y}) // Find maximum submatrix size. for (var i = 0; i < R; ++i) ans = Math.max(ans, b[i] * (R - i)); } return ans; } // Return maximum size submatrix with column // swap allowed. function solveColumnSwap( dwn) { let b = new Array(C).fill(0) let ans = 0; for (var i = 0; i < R; ++i) { // Copying the row. for (var j = 0; j < C; ++j) b[j] = dwn[i][j]; // Sort the copied array b.sort(function(x, y) { return x - y}) // Find maximum submatrix size. for (var i = 0; i < C; ++i) ans = Math.max(ans, b[i] * (C - i)); } return ans; } function findMax1s( mat) { let ryt = new Array(R + 2) let dwn = new Array(R + 2) for (var i = 0; i < R + 2; i++) { ryt[i] = new Array(C + 2).fill(0) dwn[i] = new Array(C + 2).fill(0) } precompute(mat, ryt, dwn); // Solving for row swap and column swap rswap = solveRowSwap(ryt); cswap = solveColumnSwap(dwn); // Comparing both. if (rswap > cswap) console.log("Row Swap\n" + rswap) else console.log("Column Swap\n" + cswap); } // Driven Program let mat= [[ 0, 0, 0 ], [ 1, 1, 0 ], [ 1, 1, 0 ], [ 0, 0, 0 ], [ 1, 1, 0 ]]; findMax1s(mat); // This code is contributed by phasing17. |
Output
Row Swap 6
Time Complexity: O(R*C* log(C))
Auxiliary Space: O(R*C)
This article is contributed by Anuj Chauhan. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
