2D Archives - Huahua's Tech Road

Given a 2D grid of 0s and 1s, return the number of elements in the largest square subgrid that has all 1s on its border, or 0 if such a subgrid doesn’t exist in the grid.

Example 1:

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 9

Example 2:

Input: grid = [[1,1,0,0]]
Output: 1

Constraints:

1 <= grid.length <= 100
1 <= grid[0].length <= 100
grid[i][j] is 0 or 1

Solution: DP

Compute the sums of all rectangles that has left-top corner at (0, 0) in O(m*n) time.
For each square and check whether its borders are all ones in O(1) time.

Time complexity: O(m*n*min(m,n))
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

int largest1BorderedSquare(vector<vector<int>>& grid) {

int n = grid.size();

int m = grid[0].size();

vector<vector<int>> dp(n + 1, vector<int>(m + 1));

for (int i = 1; i <= n; ++i)

for (int j = 1; j <= m; ++j)

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + grid[i - 1][j - 1];

for (int len = min(n, m); len > 0; --len)

for (int x1 = 1, x2 = x1 + len - 1; x2 <= m; ++x1, ++x2)

for (int y1 = 1, y2 = y1 + len - 1; y2 <= n; ++y1, ++y2)

if (getArea(x1, y1, x2, y1, dp) == len

&& getArea(x1, y1, x1, y2, dp) == len

&& getArea(x1, y2, x2, y2, dp) == len

&& getArea(x2, y1, x2, y2, dp) == len)

return len * len;

return 0;

}

private:

int getArea(int x1, int y1, int x2, int y2, const vector<vector<int>>& dp) {

return dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 - 1][x1 - 1];

}

};

Solution: DP

Time complexity: O(m^2*n)
Space complexity: O(mn)

dp[i][j] := max length of all 1 sequence ends with col j, at the i-th row.
transition:
dp[i][j] = 0 if matrix[i][j] == ‘0’
= dp[i][j-1] + 1 if matrix[i][j] == ‘1’

C++

class Solution {

public:

int maximalRectangle(vector<vector<char> > &matrix) {

int r = matrix.size();

if (r == 0) return 0;

int c = matrix[0].size();

// dp[i][j] := max len of all 1s ends with col j at row i.

vector<vector<int>> dp(r, vector<int>(c));

for (int i = 0; i < r; ++i)

for (int j = 0; j < c; ++j)

dp[i][j] = (matrix[i][j] == '1') ? (j == 0 ? 1 : dp[i][j - 1] + 1) : 0;

int ans = 0;

for (int i = 0; i < r; ++i)

for (int j = 0; j < c; ++j) {

int len = INT_MAX;

for (int k = i; k < r; k++) {

len = min(len, dp[k][j]);

if (len == 0) break;

ans = max(len * (k - i + 1), ans);

}

return ans;

}

};

Posts tagged as “2D”

花花酱 LeetCode 1139. Largest 1-Bordered Square

Solution: DP

C++

花花酱 LeetCode 85. Maximal Rectangle

Solution: DP

C++