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”

SIDDHANT
package TCS;

import java.util.Scanner;

public class Prog1 {
public static void main(String[] args) {
int 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}};
printArray(M);

}

static void printArray(int[][] M)
{
int max_of_s, max_i, max_j;
int i,j;
int R=M.length;
int C= M[0].length;
int S[][]=new int[R][C];

//copy first row from M to S
for(j=0;j<C;j++)
{
S[0][j]=M[0][j];
}

//copy first column from M to S
for(i=1;i<R;i++)
{
S[i][0]=M[i][0];
}

//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] = Math.min(S[i][j-1],Math.min(S[i-1][j], S[i-1][j-1])) + 1;
else if(M[i][j]==0)
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 max_i – max_of_s; i–)
{
for(j = max_j; j > max_j – max_of_s; j–)
{
System.out.print(M[i][j] + ” “);
}
System.out.println();
}
}
}

0

Log in to Reply
Avirup
#include
using namespace std;

int maxSubArray(int *arr1,int r,int c1)
{
int *sum=new int[r*c1];
int s=1;
for(int i=0;i<r;i++)
{
for(int j=0;j<c1;j++)
{
if(i==0||j==0)
{
sum[i*c1+j]=arr1[i*c1+j];
}
else
{
if(arr1[i*c1+j]==1)
{
int c=i-1;
int d=j-1;
sum[i*c1+j]=((sum[c*c1+d]<sum[i*c1+d])?((sum[c*c1+d]<sum[c*c1+j])?sum[c*c1+d]:sum[c*c1+j]):((sum[i*c1+d]s)
s=sum[i*c1+j];
}
else
{
sum[i*c1+j]=0;
}
}
}
}
return s;
}
int main()
{
int r,c,i,j;
cin>>r>>c;
int *arr=new int[r*c];
for(i=0;i<r;i++)
{
for(j=0;j>arr[i*c+j];
}
}
int s=maxSubArray(arr,r,c);
for(i=0;i<s;i++)
{
for(j=0;j<s;j++)
{
cout<<"1 ";
}
cout<<"\n";
}
return 0;
}

0

Log in to Reply
Sudarshan
// Maximum size square sub-matrix with all 1s

#include
#define bool int
#define R 6
#define C 5

/* 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;
}

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 max_i – max_of_s; i–)
{
for (j = max_j; j > max_j – max_of_s; j–)
{
printf(“%d “, M[i][j]);
}
printf(“\n”);
}
}

/* Driver function to test above functions */
int main()
{
bool M[R][C] = {{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}};

printMaxSubSquare(M);
return 0;
}

1

Log in to Reply
Shubhadeep
// JAVA Code for Maximum size square
// sub-matrix with all 1s
public class MaxSqMatrix {
// method for Maximum size square sub-matrix with all 1s
static void printMaxSubSquare(int M[][])
{
int i, j;
int R = M.length; // no of rows in M[][]
int C = M[0].length; // no of columns in M[][]
int S[][] = new int[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] = Math.min(S[i][j – 1],
Math.min(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 max_i – max_of_s; i–) {
for (j = max_j; j > max_j – max_of_s; j–) {
System.out.print(M[i][j] + ” “);
}
System.out.println();
}
}

// Driver program
public static void main(String[] args)
{
int 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

Log in to Reply
Shruti
public class Solution {
public int solve(int[][] M) {
int R= M.length;
int C= M[0].length;
int[][] S = new int[R][C];
for(int j=0;j<C;j++){
S[0][j]=M[0][j];
}
for(int i=0;i<R;i++){
S[i][0]=M[i][0];
}
for(int i=1;i<R;i++){
for(int j=1;j<C;j++){
if(M[i][j]==0){
S[i][j]=0;
}
else{
int min= Math.min(S[i][j-1],Math.min(S[i-1][j],S[i-1][j-1]))+1;
S[i][j]=min;
}
}
}
int largest= Integer.MIN_VALUE;
for(int i=0;i<R;i++){
for(int j=0;jlargest) largest= S[i][j];
}
}
return largest*largest;
}
}

0

Log in to Reply
Debparna
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
String li[] = str.split(” “);
int R = Integer.parseInt(li[0]);
int C = Integer.parseInt(li[1]);
int arr[][] = new int[R][C];
for(int i=0;i<R;i++){
str = sc.nextLine();
li = str.split(" ");
for(int j=0;j<C;j++){
arr[i][j] = Integer.parseInt(li[j]);
}
}

int dp[][] = new int[R][C];
for(int i=0;i<C;i++){
dp[R-1][i] = arr[R-1][i];
}
for(int i=0;i=0;i–){
for(int j=C-2;j>=0;j–){
if(arr[i][j]==0){
dp[i][j] = 0;
}else{
dp[i][j] = 1 + (dp[i][j+1]<dp[i+1][j]?
(dp[i][j+1]<dp[i+1][j+1]?dp[i][j+1]:dp[i+1][j+1]):
(dp[i+1][j] max){
max = dp[i][j]; r = i; c=j;
}
}
}
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
System.out.print(dp[i][j]+" ");
}
System.out.println();
}
for(int i=r;i<r+max;i++){
for(int j=c;j<c+max;j++){
System.out.print(arr[i][j]+ " ");
}
System.out.println();
}
}
}

0

Log in to Reply
gaurav
Java Solution:
/******************************************************************************

Online Java Compiler.
Code, Compile, Run and Debug java program online.
Write your code in this editor and press “Run” button to execute it.

*******************************************************************************/
import java.util.*;
public class Main
{
public static void main(String[] args) {
//Scanner sc = new Scanner(System.in);
/*int 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}};*/
int M[][] = {{0, 1, 1, 0, 1},
{0, 1, 1, 0, 0},
{1, 1, 0, 0, 0},
{1, 1, 1, 0, 1},
{0, 0, 0, 0, 0}};
printMaxSubSquare(M);
}
public static void printMaxSubSquare(int M[][]){
int i,j;
int R = M.length;
int C = M[0].length;

int s[][]=new int[R][C];
for(i=0;i<R;i++)
{
s[i][0]=M[i][0];
}
for(j=0;j<C;j++)
{
s[0][j]=M[0][j];
}

for(i=1;i<R;i++){
for(j=1;j<C;j++){
if(M[i][j]==1)
s[i][j]=Math.min((s[i-1][j]),Math.min(s[i][j-1],s[i-1][j-1]))+1;
else
s[i][j]=0;
}
}
int max_c=0,max_r=0,max_of_s=s[0][0];
for(i=0;i<R;i++){
for(j=0;j<C;j++){
if(max_of_smax_r-max_of_s;i–){
for(j=max_c;j>max_c-max_of_s;j–){
System.out.print(M[i][j]+” “);
}
System.out.println();
}
}
}

0

Log in to Reply
Shubham
Python solution for this problem:
def findSquareMatrix(M):
s = [[0 for j in range(len(i))]for i in M]
for i in range(len(M[0])):
s[0][i] = M[0][i]
for j in range(len(M)):
s[j][0] = M[j][0]
for i in range(1,len(M)):
for j in range(1,len(M[i])):
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
max_s = s[0][0]
max_i = 0
max_j = 0
for i in range(len(M)):
for j in range(len(M[0])):
if(max_s<s[i][j]):
max_s = s[i][j]
max_i = i
max_j = j
for i in range(max_i,max_i-max_s,-1):
for j in range(max_j,max_j-max_s,-1):
print(M[i][j],end = ' ')
print()

n = int(input("Enter number of rows and columns: "))
matrix = []
for i in range(n):
matrix.append(list(map(int,input().strip().split())))
findSquareMatrix(matrix)

4

Log in to Reply
Yokesh Rana
Java Solution For this problem
package test;

import java.util.Scanner;

public class max_size_subarray {
static int[][] t;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int x=sc.nextInt(),y=sc.nextInt();

int[][] a=new int[x][y];

for(int i=0;i<x;i++) {
for(int j=0;j<y;j++) {
a[i][j]=sc.nextInt();
}
}
t=new int[x][y];
int max=-1;
for(int i=0;i<x;i++)
for(int j=0;jmax)
max=t[i][j];
}
System.out.println(max+1);
}

private static int maxsizesubaary_matrix(int[][] a, int i, int j, int x, int y) {
if(i==x-1||j==y-1)
return t[i][j];
if(a[i][j+1]==1&&a[i+1][j]==1&&a[i+1][j+1]==1) {
if(t[i+1][j+1]==0)
t[i][j]=1+maxsizesubaary_matrix(a, i+1, j+1,x,y);
else
t[i][j]=1+t[i+1][j+1];
}
return t[i][j];
}
}

0

Log in to Reply
Bakwas Insaan
My dp solution
import java.io.*;
import java.util.*;
class problem2{
public static void main(String[] args){
Scanner s= new Scanner(System.in);
int m= s.nextInt();
int n= s.nextInt();
int[][] mat= new int[m][n];
for(int i= 0;i<m;i++){
for(int j= 0;j<n;j++){
mat[i][j]= s.nextInt();
}
}
int[][] dp= new int[m+1][n+1];
for(int i= 0;i<m;i++){
dp[i][0]= 0;
}
for(int i= 0;i<n;i++){
dp[0][i]= 0;
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(mat[i-1][j-1]==1){
dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1;
}
}
}
int max=Integer.MIN_VALUE;
for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
if(max<dp[i][j]){
max=dp[i][j];
}

}

}
System.out.println(max);

}
public static int min(int a,int b,int c){
if(a<b){
if(a<c){
return a;
}
else{
return c;
}
}
else{
return b;
}

}
}

0

Log in to Reply
varaprasad koluboyina
this is my code in java
package test;
import java.util.Scanner;
public class tcs {
int [][]arr;
int row,column;
int max;
tcs()
{
Scanner scan=new Scanner(System.in);
row=scan.nextInt();
column=scan.nextInt();
arr=new int[row][column];
for(int i=0;i<row;i++)
{
for(int j=0;j<column;j++)
{
arr[i][j]=scan.nextInt();
}
}
max=0;
}
void summer(int i,int j)
{

int flag=1;
int sum;
while(flag<=column-j)
{

sum=0;
for(int k=i;k<flag+i;k++)
{
for(int l=j;l<flag+j;l++)
{
sum+=arr[k][l];
}

}
if(sum==(flag*flag))
{
if(max<flag) max=flag;
flag++;
}
else
{
return;
}
}
}
void calc()
{
for(int i=0;i<(row-max);i++)
{
for(int j=0;j<column-max;j++)
{
if(arr[i][j]==1)
{
summer(i,j);
}
}
}
}
public static void main(String []args)
{
tcs t=new tcs();
t.calc();
System.out.println(t.max);
}
}

0

Log in to Reply
Shivangi Mishra
is it mandatory to code in c/c++or java??can’t we use python?

0

Log in to Reply

Prep Insta
You can use python as well.

7

Log in to Reply

Geetha
matrix=[]
a=[]
n=int(input())
for _ in range(n):
matrix.append(list(map(int,input().split())))
for i in matrix:
a.append(i.count(1))
print([[1]*a[0]]*n)

0

Log in to Reply