Formatted question description: https://leetcode.ca/all/1139.html

1139. Largest 1-Bordered Square (Medium)

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

Related Topics:
Dynamic Programming

Solution 1. Matrix Prefix Sum

// OJ: https://leetcode.com/problems/largest-1-bordered-square/
// Time: O(MN * min(M, N))
// Space: O(MN)
class Solution {
    inline int getCount(vector<vector<int>> &cnt, int a, int b, int c, int d) {
        return cnt[c + 1][d + 1] - cnt[a][d + 1] - cnt[c + 1][b] + cnt[a][b];
    }
public:
    int largest1BorderedSquare(vector<vector<int>>& G) {
        int M = G.size(), N = G[0].size(), ans = 0;
        vector<vector<int>> cnt(M + 1, vector<int>(N + 1));
        for (int i = 0; i < M; ++i) {
            int sum = 0;
            for (int j = 0; j < N; ++j) {
                sum += G[i][j];
                cnt[i + 1][j + 1] = cnt[i][j + 1] + sum;
            }
        }
        for (int a = 0; a < M; ++a) {
            for (int b = 0; b < N; ++b) {
                if (G[a][b] == 0) continue;
                ans = max(ans, 1);
                for (int len = 2; a + len - 1 < M && b + len - 1 < N; ++len) {
                    int c = a + len - 1, d = b + len - 1;
                    if (getCount(cnt, a, b, c, d) - getCount(cnt, a + 1, b + 1, c - 1, d - 1) != (c - a) * 2 + (d - b) * 2) continue;
                    ans = max(ans, len * len);
                }
            }
        }
        return ans;
    }
};

Solution 2. Prefix Sum per Row and Column

// OJ: https://leetcode.com/problems/largest-1-bordered-square/
// Time: O(MN * min(M, N))
// Space: O(MN)
class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& G) {
        int M = G.size(), N = G[0].size(), ans = 0;
        vector<vector<int>> row(M, vector<int>(N + 1)), col(M + 1, vector<int>(N));
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) row[i][j + 1] = row[i][j] + G[i][j];
        }
        for (int j = 0; j < N; ++j) {
            for (int i = 0; i < M; ++i) col[i + 1][j] = col[i][j] + G[i][j];
        }
        for (int a = 0; a < M; ++a) {
            for (int b = 0; b < N; ++b) {
                for (int len = 1; a + len - 1 < M && b + len - 1 < N; ++len) {
                    int c = a + len - 1, d = b + len - 1;
                    if (G[a][d] == 0 || G[c][b] == 0) break;
                    if (row[c][d + 1] - row[c][b] != len || col[c + 1][d] - col[a][d] != len) continue;
                    ans = max(ans, len * len);
                }
            }
        }
        return ans;
    }
};

Optimizations based on the above solution:

  • The row and column indexes a and b can ends at M - ans and N - ans. Greater row/column indexes are impossible to get better answer.
  • Instead of scanning from len = 1 every time, start from len = {previous longest valid length} + 1.
// OJ: https://leetcode.com/problems/largest-1-bordered-square/
// Time: O(MN * min(M, N))
// Space: O(MN)
class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& G) {
        int M = G.size(), N = G[0].size(), ans = 0;
        vector<vector<int>> row(M, vector<int>(N + 1)), col(M + 1, vector<int>(N));
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) row[i][j + 1] = row[i][j] + G[i][j];
        }
        for (int j = 0; j < N; ++j) {
            for (int i = 0; i < M; ++i) col[i + 1][j] = col[i][j] + G[i][j];
        }
        for (int a = 0; a < M - ans; ++a) {
            for (int b = 0; b < N - ans; ++b) {
                for (int len = ans + 1; a + len - 1 < M && b + len - 1 < N; ++len) {
                    int c = a + len - 1, d = b + len - 1;
                    if (row[a][d + 1] - row[a][b] != len || col[c + 1][b] - col[a][b] != len) break;
                    if (row[c][d + 1] - row[c][b] != len || col[c + 1][d] - col[a][d] != len) continue;
                    ans = max(ans, len);
                }
            }
        }
        return ans * ans;
    }
};

Java

  • class Solution {
        public int largest1BorderedSquare(int[][] grid) {
            int maxSide = 0;
            int rows = grid.length, columns = grid[0].length;
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < columns; j++) {
                    if (grid[i][j] == 1) {
                        maxSide = Math.max(maxSide, 1);
                        int curMaxSide = Math.min(rows - i, columns - j);
                        for (int k = 1; k < curMaxSide; k++) {
                            if (grid[i][j + k] == 0 || grid[i + k][j] == 0)
                                break;
                            if (grid[i + k][j + k] == 0)
                                continue;
                            boolean flag = true;
                            for (int m = 1; m < k; m++) {
                                if (grid[i + k][j + m] == 0 || grid[i + m][j + k] == 0) {
                                    flag = false;
                                    break;
                                }
                            }
                            if (flag)
                                maxSide = Math.max(maxSide, k + 1);
                        }
                    }
                }
            }
            return maxSide * maxSide;
        }
    }
    
  • // OJ: https://leetcode.com/problems/largest-1-bordered-square/
    // Time: O(MN * min(M, N))
    // Space: O(MN)
    class Solution {
        inline int getCount(vector<vector<int>> &cnt, int a, int b, int c, int d) {
            return cnt[c + 1][d + 1] - cnt[a][d + 1] - cnt[c + 1][b] + cnt[a][b];
        }
    public:
        int largest1BorderedSquare(vector<vector<int>>& G) {
            int M = G.size(), N = G[0].size(), ans = 0;
            vector<vector<int>> cnt(M + 1, vector<int>(N + 1));
            for (int i = 0; i < M; ++i) {
                int sum = 0;
                for (int j = 0; j < N; ++j) {
                    sum += G[i][j];
                    cnt[i + 1][j + 1] = cnt[i][j + 1] + sum;
                }
            }
            for (int a = 0; a < M; ++a) {
                for (int b = 0; b < N; ++b) {
                    if (G[a][b] == 0) continue;
                    ans = max(ans, 1);
                    for (int len = 2; a + len - 1 < M && b + len - 1 < N; ++len) {
                        int c = a + len - 1, d = b + len - 1;
                        if (getCount(cnt, a, b, c, d) - getCount(cnt, a + 1, b + 1, c - 1, d - 1) != (c - a) * 2 + (d - b) * 2) continue;
                        ans = max(ans, len * len);
                    }
                }
            }
            return ans;
        }
    };
    
  • # 1139. Largest 1-Bordered Square
    # https://leetcode.com/problems/largest-1-bordered-square/
    
    class Solution:
        def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
            res = 0
            rows, cols = len(grid), len(grid[0])
            
            def check(x, y):
                return 0 <= x < rows and 0 <= y < cols
            
            def dfs(i, j, size):
                res = 1
                isValid = canContinue = True
                mx, my = i + size, j + size
                
                if not check(mx, my): return res
                
                for dy in range(j, my + 1):
                    if check(i, dy) and check(mx, dy) and grid[i][dy] == 0 or grid[mx][dy] == 0:
                        isValid = False
                        if grid[i][dy] == 0: 
                            canContinue = False
                
                for dx in range(i, mx + 1):
                    if check(dx, j) and check(dx, my) and grid[dx][j] == 0 or grid[dx][my] == 0:
                        isValid = False
                        if grid[dx][j] == 0:
                            canContinue = False
                        
                if isValid:
                    res = max(res, (size + 1) * (size + 1))
    
                if canContinue and check(i + size + 1, j + size + 1):
                    res = max(res, dfs(i, j, size + 1))
                
                return res 
            
            for i in range(rows):
                for j in range(cols):
                    if grid[i][j] == 1:
                        res = max(res, dfs(i, j, 0))
            
            return res
    
    

All Problems

All Solutions