Tutorialspoint.dev

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



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])
{
    // 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.
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 " << 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

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter