221. Maximal Square

Posted on Edited on In

221. Maximal Square

Description

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.

Example 1:

1
2
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

1
2
Input: matrix = [["0","1"],["1","0"]]
Output: 1

Example 3:

1
2
Input: matrix = [["0"]]
Output: 0

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] is '0' or '1'.

Hints/Notes

Solution

Language: C++

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
class Solution {
public:
    vector<vector<int>> preSum;

    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        preSum.resize(m + 1, vector<int>(n + 1, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int val = matrix[i][j] - '0';
                preSum[i + 1][j + 1] = preSum[i][j + 1] + preSum[i + 1][j] + val - preSum[i][j];
            }
        }
        int cur = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = cur + 1; k <= min(i, j); k++) {
                    if (preSum[i][j] - preSum[i - k][j] - preSum[i][j - k] + preSum[i - k][j - k] == k * k) {
                        cout << i << " " << j << endl;
                        cur = k;
                    } else {
                        break;
                    }
                }
            }
        }
        return cur * cur;
    }
};