1139. Largest 1-Bordered Square

Description

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

Solutions

Solution 1: Prefix Sum + Enumeration

We can use the prefix sum method to preprocess the number of consecutive 1s down and to the right of each position, denoted as down[i][j] and right[i][j].

Then we enumerate the side length \(k\) of the square, starting from the largest side length. Then we enumerate the upper left corner position \((i, j)\) of the square. If it meets the condition, we can return \(k^2\).

The time complexity is \(O(m \times n \times \min(m, n))\), and the space complexity is \(O(m \times n)\). Here, \(m\) and \(n\) are the number of rows and columns of the grid, respectively.

Python3JavaC++Go

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        down = [[0] * n for _ in range(m)]
        right = [[0] * n for _ in range(m)]
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if grid[i][j]:
                    down[i][j] = down[i + 1][j] + 1 if i + 1 < m else 1
                    right[i][j] = right[i][j + 1] + 1 if j + 1 < n else 1
        for k in range(min(m, n), 0, -1):
            for i in range(m - k + 1):
                for j in range(n - k + 1):
                    if (
                        down[i][j] >= k
                        and right[i][j] >= k
                        and right[i + k - 1][j] >= k
                        and down[i][j + k - 1] >= k
                    ):
                        return k * k
        return 0

class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] down = new int[m][n];
        int[][] right = new int[m][n];
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (grid[i][j] == 1) {
                    down[i][j] = i + 1 < m ? down[i + 1][j] + 1 : 1;
                    right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
                }
            }
        }
        for (int k = Math.min(m, n); k > 0; --k) {
            for (int i = 0; i <= m - k; ++i) {
                for (int j = 0; j <= n - k; ++j) {
                    if (down[i][j] >= k && right[i][j] >= k && right[i + k - 1][j] >= k
                        && down[i][j + k - 1] >= k) {
                        return k * k;
                    }
                }
            }
        }
        return 0;
    }
}

class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int down[m][n];
        int right[m][n];
        memset(down, 0, sizeof down);
        memset(right, 0, sizeof right);
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (grid[i][j] == 1) {
                    down[i][j] = i + 1 < m ? down[i + 1][j] + 1 : 1;
                    right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
                }
            }
        }
        for (int k = min(m, n); k > 0; --k) {
            for (int i = 0; i <= m - k; ++i) {
                for (int j = 0; j <= n - k; ++j) {
                    if (down[i][j] >= k && right[i][j] >= k && right[i + k - 1][j] >= k
                        && down[i][j + k - 1] >= k) {
                        return k * k;
                    }
                }
            }
        }
        return 0;
    }
};

func largest1BorderedSquare(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    down := make([][]int, m)
    right := make([][]int, m)
    for i := range down {
        down[i] = make([]int, n)
        right[i] = make([]int, n)
    }
    for i := m - 1; i >= 0; i-- {
        for j := n - 1; j >= 0; j-- {
            if grid[i][j] == 1 {
                down[i][j], right[i][j] = 1, 1
                if i+1 < m {
                    down[i][j] += down[i+1][j]
                }
                if j+1 < n {
                    right[i][j] += right[i][j+1]
                }
            }
        }
    }
    for k := min(m, n); k > 0; k-- {
        for i := 0; i <= m-k; i++ {
            for j := 0; j <= n-k; j++ {
                if down[i][j] >= k && right[i][j] >= k && right[i+k-1][j] >= k && down[i][j+k-1] >= k {
                    return k * k
                }
            }
        }
    }
    return 0
}

1139. Largest 1-Bordered Square

Description

Solutions

Solution 1: Prefix Sum + Enumeration

Comments