-
Notifications
You must be signed in to change notification settings - Fork 15
/
Copy pathMaximalSquare.js
63 lines (59 loc) · 1.75 KB
/
MaximalSquare.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
* @author Anirudh Sharma
*
* Given an m x n binary matrix filled with 0's and 1's, find the largest square containing
* only 1's and return its area.
*
* Constraints:
*
* m == matrix.length
* n == matrix[i].length
* 1 <= m, n <= 300
* matrix[i][j] is '0' or '1'.
*/
const maximalSquare = (matrix) => {
// Special case
if (matrix === undefined || matrix.length === 0) {
return 0;
}
// Rows and columns of the matrix
const m = matrix.length;
const n = matrix[0].length;
// Lookup table to store the size of the sub-matrix
// of which current cell is the bottom right corner
const lookup = Array.from(Array(m + 1), () => Array(n + 1).fill(0));
// Variable to keep track of biggest square matrix seen so far
let maxSize = 0;
// Loop through the matrix and populate the lookup table
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
// If the current cell has 1, then we can consider
// it as a valid case and try to make it as the part
// of the valid sub matrix
if (matrix[i - 1][j - 1] === '1') {
lookup[i][j] = Math.min(lookup[i - 1][j], Math.min(lookup[i - 1][j - 1], lookup[i][j - 1])) + 1;
maxSize = Math.max(maxSize, lookup[i][j]);
}
}
}
return maxSize * maxSize;
};
const main = () => {
let matrix = [
['1', '0', '1', '0', '0'],
['1', '0', '1', '1', '1'],
['1', '1', '1', '1', '1'],
['1', '0', '0', '1', '0']
];
console.log(maximalSquare(matrix));
matrix = [
['0', '1'],
['1', '0']
];
console.log(maximalSquare(matrix));
matrix = [
['0']
];
console.log(maximalSquare(matrix));
};
main();