DEV Community

Cover image for How to find the biggest square in matrice ?
Yann
Yann

Posted on

How to find the biggest square in matrice ?

Yesterday, in a clash of code on codingGame, I came across the maximal square problem. It was a huge defeat. But, after several hours on this topics I defenitly understand how to become a wizard with dynamic programming:

So, Imagine you have this matrice :

0 1 1 1 0
0 1 1 1 0
0 1 1 1 0

How can you find the biggest square of 1s (with code, of course) ?

First, we can represent the matrice with an array :

const m = [[0,0,0], [1,1,1], [1,1,1], [1,1,1], [0,0,0]]
Enter fullscreen mode Exit fullscreen mode

Then, we can start by write a function like this :

function getSquareSideLength(m, search) {

const rows = m.length
const cols = m[0].length

for (let i = 0; i < rows; i++) {
 for (let j = 0; i < cols; i++) {
 ...
 }
}
Enter fullscreen mode Exit fullscreen mode

Now it's a little more complicated, we need to save the count state between iterations, we need a second matrice. With this second matrice we can follow the solution illustrate below :

Image description

In Javascript :

function getSquareSideLength(m,s) {
    // copy must be [[0,0,0,0], [1,1,1,0], [1,1,1,0], [1,1,1,0], [0,0,0,0], [0,0,0,0]]
    const copy = JSON.parse(JSON.stringify(m)).map(c => { c.fill(0).push(0); return c }) // for convenience, we add an extra all zero column and row
    copy[copy.length] = [...copy[copy.length - 1]]
    const rows = m.length
    const cols = m[0].length

    let res = 0

    for (let i = 1; i <= rows; i++) {
        for (let j = 1; j <= cols; j++) {
            if (m[i-1][j-1] == s) {
                copy[i][j] = Math.min(copy[i][j - 1], copy[i - 1][j], copy[i - 1][j - 1]) + 1;
                res = Math.max(res, copy[i][j]);
            }
        }
    }

     return res; 
}
Enter fullscreen mode Exit fullscreen mode

This solution its not perfect but understandable. I you want to have the perfect response of this problem, check the third solution on this article. It would be nice to have the third solution in Javascript, someone can do it ?

Top comments (0)