LeetCode - Algorithms - 221. Maximal Square

Problem

221. Maximal Square

Java

dynamic programming

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
class Solution {
    public int maximalSquare(char[][] matrix) {
        final int[][] D = {
                {-1, 0},  // up
                {0, -1},  // left
                {-1, -1}  // diagonal
        };
        int h = matrix.length;
        int w = matrix[0].length;
        int[][] countMatrix = new int[h][w];
        for (int i = 0; i < w; i++) {
            countMatrix[0][i] = matrix[0][i] == '1' ? 1 : 0;
        }
        if (h > 1) {
            for (int j = 1; j < h; j++) {
                countMatrix[j][0] = matrix[j][0] == '1' ? 1 : 0;
            }
            for (int i = 1; i < h; i++) {
                for (int j = 1; j < w; j++) {
                    if (matrix[i][j] == '1') {
                        int minCount = Integer.MAX_VALUE;
                        for (int k = 0; k < 3; k++) {
                            int x = i + D[k][0];
                            int y = j + D[k][1];
                            if (minCount > countMatrix[x][y])
                                minCount = countMatrix[x][y];
                        }
                        countMatrix[i][j] = minCount + 1;
                    } else {
                        countMatrix[i][j] = 0;
                    }
                }
            }
        }
        int maxCount = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (countMatrix[i][j] > maxCount)
                    maxCount = countMatrix[i][j];
            }
        }
        return maxCount * maxCount;       
    }
}

Submission Detail

  • 74 / 74 test cases passed.
  • Runtime: 5 ms, faster than 51.51% of Java online submissions for Maximal Square.
  • Memory Usage: 49 MB, less than 8.01% of Java online submissions for Maximal Square.