// JavaScript code for Maximum size square
// sub-matrix with all 1s
// (space optimized solution)
const R = 4
const C = 3
function printMaxSubSquare(M)
{
let Max = 0
let S = new Array(2)
// set all elements of S to 0 first
for(let i=0;i<2;i++){
S[i] = new Array(C).fill(0)
}
// Construct the entries
for (let i = 0; i < R;i++)
for (let j = 0; j < C;j++){
// Compute the entrie at the current position
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]));
// Save the last entrie and add the new one
S[0][j] = S[1][j];
S[1][j] = Entrie;
// Keep track of the max square length
Max = Math.max(Max, Entrie);
}
// Print the square
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>")
}
}
// Driver code
const M = [ [1, 1, 1],
[1, 1, 1],
[0, 0, 1],
[0, 1, 0]]
printMaxSubSquare(M)
// This code is contributed by shinjanpatra
