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]]
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++) {
...
}
}
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 :
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;
}
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)