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:
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:
Input: matrix = [["0","1"],["1","0"]] Output: 1
Example 3:
Input: matrix = [["0"]] Output: 0
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 300matrix[i][j]is'0'or'1'.
Companies:
Amazon, Visa, Microsoft, IBM, Google, Twitter, Apple, Booking.com, Indeed
Related Topics:
Array, Dynamic Programming, Matrix
Similar Questions:
// OJ: https://leetcode.com/problems/maximal-square/
// Author: github.com/lzl124631x
// Time: O((MN)^2)
// Space: O(1)
class Solution {
public:
int maximalSquare(vector<vector<char>>& A) {
if (A.empty() || A[0].empty()) return 0;
int M = A.size(), N = A[0].size(), ans = 0;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
int k = 0;
bool stop = false;
for (; i + k < M && j + k < N; ++k) {
for (int t = 0; t < k + 1 && !stop; ++t) {
if (A[i + t][j + k] == '0') stop = true;
}
for (int t = 0; t < k + 1 && !stop; ++t) {
if (A[i + k][j + t] == '0') stop = true;
}
if (stop) break;
}
ans = max(ans, k);
}
}
return ans * ans;
}
};This problem is trivial on 1D array.
Let row[i][j] be the length of consecutive 1s ending at A[i][j] in ith row.
Let col[i][j] be the length of consecutive 1s ending at A[i][j] in jth column.
With these two arrays, for each matrix[i][j], the side length of the square whose bottom right corner is at matrix[i][j] is at most min(row[i][j], col[i][j]). Then we keep probing the col[i][k] where k < j to keep tighten the limit.
// OJ: https://leetcode.com/problems/maximal-square/
// Author: github.com/lzl124631x
// Time: O(M * N^2)
// Space: O(MN)
class Solution {
public:
int maximalSquare(vector<vector<char>>& A) {
if (A.empty() || A[0].empty()) return 0;
int M = A.size(), N = A[0].size(), ans = 0;
vector<vector<int>> row(M, vector<int>(N, 0)), col(M, vector<int>(N, 0));
for (int i = 0; i < M; ++i) {
int start = -1;
for (int j = 0; j < N; ++j) {
if (A[i][j] == '0') start = j;
row[i][j] = j - start;
}
}
for (int j = 0; j < N; ++j) {
int start = -1;
for (int i = 0; i < M; ++i) {
if (A[i][j] == '0') start = i;
col[i][j] = i - start;
}
}
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
int end = min(row[i][j], col[i][j]), k = 0;
while (k < end) {
++k;
if (j - k < 0) break;
end = min(end, col[i][j - k]);
}
ans = max(ans, k);
}
}
return ans * ans;
}
};Let dp[i + 1][j + 1] be the side length of the maximal square whose bottom right corner is at matrix[i][j]. Then we have:
dp[i + 1][j + 1] = min(dp[i][j], dp[i][j + 1], dp[i + 1][j]) + 1
// OJ: https://leetcode.com/problems/maximal-square/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
int maximalSquare(vector<vector<char>>& A) {
int M = A.size(), N = A[0].size(), ans = 0;
vector<vector<int>> dp(M + 1, vector<int>(N + 1));
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (A[i][j] == '0') continue;
dp[i + 1][j + 1] = 1 + min({ dp[i][j], dp[i + 1][j], dp[i][j + 1] });
ans = max(ans, dp[i + 1][j + 1]);
}
}
return ans * ans;
}
}; dp[i][j] dp[i][j + 1]
\ |
dp[i+1][j] -- dp[i + 1][j + 1]
Given the dependency above, we can use a 2 * N array to store the DP values.
// OJ: https://leetcode.com/problems/maximal-square/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(N)
class Solution {
public:
int maximalSquare(vector<vector<char>>& A) {
int M = A.size(), N = A[0].size(), ans = 0;
vector<vector<int>> dp(2, vector<int>(N + 1));
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
dp[(i + 1) % 2][j + 1] = A[i][j] == '0' ? 0 : min({ dp[i % 2][j], dp[i % 2][j + 1], dp[(i + 1) % 2][j] }) + 1;
ans = max(ans, dp[(i + 1) % 2][j + 1]);
}
}
return ans * ans;
}
};Or via swapping arrays.
// OJ: https://leetcode.com/problems/maximal-square/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(N)
class Solution {
public:
int maximalSquare(vector<vector<char>>& A) {
int M = A.size(), N = A[0].size(), ans = 0;
vector<int> dp(N + 1), next;
for (int i = 0; i < M; ++i) {
next.assign(N + 1, 0);
for (int j = 0; j < N; ++j) {
if (A[i][j] == '0') continue;
next[j + 1] = 1 + min({ dp[j], dp[j + 1], next[j] });
ans = max(ans, next[j + 1]);
}
swap(next, dp);
}
return ans * ans;
}
};Or: Use a prev variable to store the dp[i][j], then we can further reduce the dp array to 1D array.
// OJ: https://leetcode.com/problems/maximal-square/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(N)
class Solution {
public:
int maximalSquare(vector<vector<char>>& A) {
int M = A.size(), N = A[0].size(), ans = 0;
vector<int> dp(N + 1, 0);
for (int i = 0; i < M; ++i) {
int prev = 0;
for (int j = 0; j < N; ++j) {
int cur = dp[j + 1];
if (A[i][j] == '1') dp[j + 1] = 1 + min({ prev, dp[j], dp[j + 1] });
else dp[j + 1] = 0;
prev = cur;
ans = max(ans, dp[j + 1]);
}
}
return ans * ans;
}
};