Maximum size square sub-matrix with all 1s

Algorithm:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents the size of the square sub-matrix with all 1s including M[i][j] where M[i][j] is the rightmost and bottom-most entry in sub-matrix.

1) Construct a sum matrix S[R][C] for the given M[R][C]. a) Copy first row and first columns as it is from M[][] to S[][] b) For other entries, use following expressions to construct S[][] If M[i][j] is 1 then S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1 Else /*If M[i][j] is 0*/ S[i][j] = 02) Find the maximum entry in S[R][C]3) Using the value and coordinates of maximum entry in S[i], print sub-matrix of M[][]

For the given M[R][C] in the above example, constructed S[R][C] would be:

 0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 2 2 0 1 2 2 3 1 0 0 0 0 0

The value of the maximum entry in the above matrix is 3 and the coordinates of the entry are (4, 3). Using the maximum value and its coordinates, we can find out the required sub-matrix.

C++

#include <bits/stdc++.h>

#define bool int

#define R 6

#define C 5

using namespace std;

void printMaxSubSquare(bool M[R][C])

{

int i,j;

int S[R][C];

int max_of_s, max_i, max_j;

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] = min({S[i][j-1], S[i-1][j],

S[i-1][j-1]}) + 1;

else

S[i][j] = 0;

}

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;

}

cout<<"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--)

{

cout << M[i][j] << " ";

}

cout << "\n";

}

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);

}

C

#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;

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] = min(S[i][j-1], S[i-1][j],

S[i-1][j-1]) + 1;

else

S[i][j] = 0;

}

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");

}

int min(int a, int b, int c)

{

int m = a;

if (m > b)

m = b;

if (m > c)

m = c;

return m;

}

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();

}

Java

public class GFG

{

static void printMaxSubSquare(int M[][])

{

int i,j;

int R = M.length;

int C = M[0].length;

int S[][] = new int[R][C];

int max_of_s, max_i, max_j;

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][j-1],

Math.min(S[i-1][j], S[i-1][j-1])) + 1;

else

S[i][j] = 0;

}

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;

}

System.out.println("Maximum size sub-matrix is: ");

for(i = max_i; i > 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();

}

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);

}

Python3

def printMaxSubSquare(M):

R = len(M)

C = len(M[0])

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,

for i in range(1, R):

C#

using System;

public class GFG

{

static void printMaxSubSquare(int [,]M)

{

int i,j;

int R = M.GetLength(0);

int C = M.GetLength(1);

int [,]S = new int[R,C];

int max_of_s, max_i, max_j;

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,j-1],

Math.Min(S[i-1,j], S[i-1,j-1])) + 1;

else

S[i,j] = 0;

}

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;

}

Console.WriteLine("Maximum size sub-matrix is: ");

for(i = max_i; i > max_i - max_of_s; i--)

{

for(j = max_j; j > max_j - max_of_s; j--)

{

Console.Write(M[i,j] + " ");

}

Console.WriteLine();

}

public static void Main()

{

int [,]M = new int[6,5]{{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);

}

PHP

<?php

function printMaxSubSquare($M, $R, $C)

{

$S = array(array()) ;

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] = min($S[$i][$j - 1],

$S[$i - 1][$j],

$S[$i - 1][$j - 1]) + 1;

else

$S[$i][$j] = 0;

}

$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--)

{

echo $M[$i][$j], " " ;

}

echo "\n" ;

}

# Driver code

$M = array(array(0, 1, 1, 0, 1),

array(1, 1, 0, 1, 0),

array(0, 1, 1, 1, 0),

array(1, 1, 1, 1, 0),

array(1, 1, 1, 1, 1),

array(0, 0, 0, 0, 0));

$R = 6 ;

$C = 5 ;

printMaxSubSquare($M, $R, $C);

?>

Javascript

<script>

let R = 6;

let C = 5;

function printMaxSubSquare(M) {

let i,j;

let S = [];

for ( var y = 0; y < R; y++ ) {

S[ y ] = [];

for ( var x = 0; x < C; x++ ) {

S[ y ][ x ] = 0;

}

let max_of_s, max_i, max_j;

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][j-1],Math.min( S[i-1][j],

S[i-1][j-1])) + 1;

else

S[i][j] = 0;

}

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;

}

document.write("Maximum size sub-matrix is: <br>");

for(i = max_i; i > max_i - max_of_s; i--)

{

for(j = max_j; j > max_j - max_of_s; j--)

{

document.write( M[i][j] , " ");

}

document.write("<br>");

}

let 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);

</script>

Output:

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

Time Complexity: O(m*n) where m is the number of rows and n is the number of columns in the given matrix.
Auxiliary Space: O(m*n) where m is the number of rows and n is the number of columns in the given matrix.
Algorithmic Paradigm: Dynamic Programming

Space Optimized Solution: In order to compute an entry at any position in the matrix we only need the current row and the previous row.

C++

#include <bits/stdc++.h>

using namespace std;

#define R 6

#define C 5

void printMaxSubSquare(bool M[R][C])

{

int S[2][C], Max = 0;

memset(S, 0, sizeof(S));

for (int i = 0; i < R;i++)

for (int j = 0; j < C;j++){

int Entrie = M[i][j];

if(Entrie)

if(j)

Entrie = 1 + min(S[1][j - 1], min(S[0][j - 1], S[1][j]));

S[0][j] = S[1][j];

S[1][j] = Entrie;

Max = max(Max, Entrie);

}

cout << "Maximum size sub-matrix is: \n";

for (int i = 0; i < Max; i++, cout << '\n')

for (int j = 0; j < Max;j++)

cout << "1 ";

}

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);

return 0;

}

Java

import java.util.*;

class GFG {

static int R = 6 ;

static int C = 5 ;

static void printMaxSubSquare(int M[][])

{

int S[][] = new int[2][C], Max = 0;

for (int i = 0; i < 2;i++){

for (int j = 0; j < C;j++){

S[i][j] =0;

}

for (int i = 0; i < R; i++){

for (int j = 0; j < C; j++){

int Entrie = M[i][j];

if(Entrie != 0){

if(j != 0){

Entrie = 1 + Math.min(S[1][j - 1], Math.min(S[0][j - 1], S[1][j]));}}

S[0][j] = S[1][j];

S[1][j] = Entrie;

Max = Math.max(Max, Entrie);

}

System.out.print("Maximum size sub-matrix is: \n");

for (int i = 0; i < Max; i++){

for (int j = 0; j < Max;j++){

System.out.print( "1 ");}

System.out.println();

}

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);

}

Javascript

<script>

const R = 6

const C = 5

function printMaxSubSquare(M)

{

let Max = 0

let S = new Array(2)

for(let i=0;i<2;i++){

S[i] = new Array(C).fill(0)

}

for (let i = 0; i < R;i++)

for (let j = 0; j < C;j++){

let Entrie = M[i][j];

if(Entrie)

if(j)

Entrie = 1 + Math.min(S[1][j - 1],

Math.min(S[0][j - 1], S[1][j]));

S[0][j] = S[1][j];

S[1][j] = Entrie;

Max = Math.max(Max, Entrie);

}

document.write("Maximum size sub-matrix is: ","</br>")

for (let i = 0; i < Max; i++){

for (let j = 0; j < Max;j++)

document.write("1 ")

document.write("</br>")

}

const 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)

</script>

Python3

R = 6

C = 5

def printMaxSubSquare(M):

global R,C

Max = 0

S = [[0 for col in range(C)]for row in range(2)]

for i in range(R):

for j in range(C):

Entrie = M[i][j]

if(Entrie):

if(j):

Entrie = 1 + min(S[1][j - 1],min(S[0][j - 1], S[1][j]))

S[0][j] = S[1][j]

S[1][j] = Entrie

Max = max(Max, Entrie)

print("Maximum size sub-matrix is: ")

for i in range(Max):

for j in range(Max):

print("1",end=" ")

print()

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)

C#

using System;

using System.Numerics;

using System.Collections.Generic;

public class GFG {

static int R = 6 ;

static int C = 5 ;

static void printMaxSubSquare(int[,] M)

{

int[,] S = new int[2, C];

int Maxx = 0;

for (int i = 0; i < 2;i++){

for (int j = 0; j < C;j++){

S[i, j] =0;

}

for (int i = 0; i < R; i++){

for (int j = 0; j < C; j++){

int Entrie = M[i, j];

if(Entrie != 0){

if(j != 0){

Entrie = 1 + Math.Min(S[1, j - 1], Math.Min(S[0, j - 1], S[1, j]));}}

S[0,j] = S[1,j];

S[1,j] = Entrie;

Maxx = Math.Max(Maxx, Entrie);

}

Console.Write("Maximum size sub-matrix is: \n");

for (int i = 0; i < Maxx; i++){

for (int j = 0; j < Maxx;j++){

Console.Write( "1 ");}

Console.WriteLine();

}

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);

}

Output

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

Time Complexity: O(m*n) where m is the number of rows and n is the number of columns in the given matrix. Auxiliary space: O(n) where n is the number of columns in the given matrix.

Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem

Maximum size square sub-matrix with all 1s - GeeksforGeeks (2022)

C++

C

Java

Python3

C#

PHP

Javascript

C++

Java

Javascript

Python3

C#

You might also like

❱❱LEKI TRAIL AS • Top 3 Modelle unter der Lupe

❱❱LEKI TRAIL AS - Die momentan beliebtesten Modelle im Detail!

LEKI Outlet SALE -80% ✔ LEKI günstig kaufen

Best Nordic Walking Poles of 2022 (Guide & Reviews)

Leki Voyager Trekking Poles (Pair) Reviews - Updated July 2022

Leki | Voyager | Trekking Poles

Bâtons Trail et Running : LEKI, Black Diamond, Guidetti, Swix

What to Pack for Hiking: 38 Hiking Essentials | SmarterTravel

▷ Como fazer um jornal para trabalho escolar | Actualizado agosto 2022

Acoso laboral: El desafío de animarse a denunciar y no minimizarlo – Latitud25

Latest Posts

Grypa, przeziębienie, koronawirus – jak odróżnić, po jakie leki sięgnąć?

Elder Scrolls Online: 15 Best Nightblade Builds, Ranked

Choroba wrzodowa żołądka i dwunastnicy jako skutek przewlekłego stosowania niesteroidowych leków przeciwzapalnych (NLPZ)

Antybiotyki na wrzody żołądka i dwunastnicy: instrukcja (2022)

Choroba wrzodowa żołądka i dwunastnicy – objawy, przyczyny i leczenie

Ewa Minge o przemocowym związku, kobietach w show-biznesie, seksie i samoakceptacji po "50"

Wrzody żołądka i dwunastnicy – co należy o nich wiedzieć?

Siarka organiczna (MSM) - co to jest, właściwości i skutki uboczne

najlepsze znaleziska i wpisy o #anonimowemirkowyznania w Wykop.pl

VaxigripTetra zawiesina do wstrzykiwań - działanie, dawkowanie, cena, refundacja