Question 1

September 8, 2020

Maximum size square sub-matrix with all 1s

Given a binary matrix, find out the maximum size square sub-matrix with all 1s.

For eg –  if the entered matrix is
[{1,0,0,1,0},  {1,1,1,1,1},{1,0,1,1,1}, {0,0,1,1,0} , {1,1,1,1,1}], then the output will be
[{1,1}, {1,1}, {1,1}, {1,1}]

Code for finding the maximum size square sub-matrix with all 1s

#include<stdio.h>
#define bool int
#define R 6
#define C 5

void printMaxSubSquare (bool M[R][C])
{
  int i, j;
  int S[R][C];
  int max_of_s, max_i, max_j;

/* Set first column of S[][]*/
  for (i = 0; i < R; i++)
    S[i][0] = M[i][0];


/* Set first row of S[][]*/
  for (j = 0; j < C; j++)
    S[0][j] = M[0][j];


/* Construct other entries of S[][]*/
  for (i = 1; i < R; i++)
    {
      for (j = 1; j < C; j++)
	{
	  if (M[i][j] == 1)
	    S[i][j] = min (S[i][j - 1], S[i - 1][j], S[i - 1][j - 1]) + 1;
	  else
	    S[i][j] = 0;
	}
    }


/* Find the maximum entry, and indexes of maximum entry
in S[][] */
  max_of_s = S[0][0];
  max_i = 0;
  max_j = 0;
  for (i = 0; i < R; i++)
    {
      for (j = 0; j < C; j++)
	{
	  if (max_of_s < S[i][j])
	    {
	      max_of_s = S[i][j];
	      max_i = i;
	      max_j = j;
	    }
	}
    }

  printf ("Maximum size sub-matrix is: \n");
  for (i = max_i; i > max_i - max_of_s; i--)
    {
      for (j = max_j; j > max_j - max_of_s; j--)
	{
	  printf ("%d ", M[i][j]);
	}
      printf ("\n");
    }
}


/* UTILITY FUNCTIONS */
/* Function to get minimum of three values */
int min (int a, int b, int c)
{
  int m = a;
  if (m > b)
    m = b;
  if (m > c)
    m = c;
  return m;
}


/* Driver function to test above functions */
int main ()
{
  bool M[R][C] = { {0, 1, 1, 0, 1},
  {1, 1, 0, 1, 0},
  {0, 1, 1, 1, 0},
  {1, 1, 1, 1, 0},
  {1, 1, 1, 1, 1},
  {0, 0, 0, 0, 0}
  };

  printMaxSubSquare (M);
  getchar ();
}
Output

Maximum size sub-matrix is: 
1 1 1 
1 1 1 
1 1 1

32 comments on “Question 1”


  • BODDU

    # Python3 code for Maximum size
    # square sub-matrix with all 1s

    def printMaxSubSquare(M):
    R = len(M) # no. of rows in M[][]
    C = len(M[0]) # no. of columns in M[][]

    S = []
    for i in range(R):
    temp = []
    for j in range(C):
    if i == 0 or j == 0:
    temp += M[i][j],
    else:
    temp += 0,
    S += temp,
    # here we have set the first row and first column of S same as input matrix, other entries are set to 0

    # Update other entries
    for i in range(1, R):
    for j in range(1, C):
    if (M[i][j] == 1):
    S[i][j] = min(S[i][j-1], S[i-1][j],
    S[i-1][j-1]) + 1
    else:
    S[i][j] = 0

    # Find the maximum entry and
    # indices of maximum entry in S[][]
    max_of_s = S[0][0]
    max_i = 0
    max_j = 0
    for i in range(R):
    for j in range(C):
    if (max_of_s < S[i][j]):
    max_of_s = S[i][j]
    max_i = i
    max_j = j

    print("Maximum size sub-matrix is: ")
    for i in range(max_i, max_i – max_of_s, -1):
    for j in range(max_j, max_j – max_of_s, -1):
    print(M[i][j], end=" ")
    print("")

    # Driver Program
    M = [[0, 1, 1, 0, 1],
    [1, 1, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [1, 1, 1, 1, 0],
    [1, 1, 1, 1, 1],
    [0, 0, 0, 0, 0]]

    printMaxSubSquare(M)

    0

  • chamakura chandu

    static int maxSquare(int n, int m, int mat[][]){
    // code here
    int ans=0;
    int[][] dp=new int[n+1][m+1];
    for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
    if(mat[i-1][j-1]==1){
    dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
    ans=Math.max(ans,dp[i][j]);
    }
    }
    }
    return ans;
    }

    0

  • chandrakhanth07

    def find_max_square_submatrix(matrix):
    # dp[i][j] stores the maximum size square submatrix with all 1s ending at (i, j)
    dp = [[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
    # initialize dp
    for i in range(len(matrix)):
    for j in range(len(matrix[0])):
    if matrix[i][j] == 1:
    if i == 0 or j == 0:
    dp[i][j] = 1
    else:
    dp[i][j] = min(dp[i – 1][j – 1], dp[i – 1][j], dp[i][j – 1]) + 1
    # find the maximum value in dp
    max_size = 0
    max_i, max_j = 0, 0
    for i in range(len(matrix)):
    for j in range(len(matrix[0])):
    if dp[i][j] > max_size:
    max_size = dp[i][j]
    max_i = i
    max_j = j
    # return the maximum size square submatrix with all 1s
    return matrix[max_i – max_size + 1:max_i + 1, max_j – max_size + 1:max_j + 1]
    if __name__ == ‘__main__’:
    matrix = [[1, 0, 0, 1, 0],
    [1, 1, 1, 1, 1],
    [1, 0, 1, 1, 1],
    [0, 0, 1, 1, 0],
    [1, 1, 1, 1, 1]]
    print(find_max_square_submatrix(matrix))

    0
1 2 3