Problem

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.

Examples

Example 1

1
2
3
4
5
6


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

Example 2

1
2
3
4
5
6


    
    
    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

Method 1 – Dynamic Programming for Border Counting

Intuition

To find the largest 1-bordered square, for each cell, we need to know how many consecutive 1’s are to its left and above. This allows us to quickly check if a square of a given size ending at (i, j) has all 1’s on its border.

Approach

  1. Precompute for each cell the number of consecutive 1’s to the left and above (including itself).
  2. For each cell (i, j), try all possible square sizes from largest to smallest that could end at (i, j).
  3. For a square of size k, check if the top, left, right, and bottom borders are all 1’s using the precomputed counts.
  4. Track and return the area of the largest valid square found.

Code

 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

class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size(), ans = 0;
        vector<vector<int>> left(m, vector<int>(n)), up(m, vector<int>(n));
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) {
                if (grid[i][j]) {
                    left[i][j] = (j ? left[i][j-1] : 0) + 1;
                    up[i][j] = (i ? up[i-1][j] : 0) + 1;
                }
            }
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) {
                int k = min(left[i][j], up[i][j]);
                while (k > 0) {
                    if (left[i-k+1][j] >= k && up[i][j-k+1] >= k) {
                        ans = max(ans, k*k);
                        break;
                    }
                    --k;
                }
            }
        return ans;
    }
};
 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
30
31

func largest1BorderedSquare(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    left := make([][]int, m)
    up := make([][]int, m)
    for i := range left { left[i] = make([]int, n); up[i] = make([]int, n) }
    ans := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                left[i][j] = 1
                up[i][j] = 1
                if j > 0 { left[i][j] += left[i][j-1] }
                if i > 0 { up[i][j] += up[i-1][j] }
            }
        }
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            k := left[i][j]
            if up[i][j] < k { k = up[i][j] }
            for k > 0 {
                if left[i-k+1][j] >= k && up[i][j-k+1] >= k {
                    if k*k > ans { ans = k*k }
                    break
                }
                k--
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int m = grid.length, n = grid[0].length, ans = 0;
        int[][] left = new int[m][n], up = new int[m][n];
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == 1) {
                    left[i][j] = (j > 0 ? left[i][j-1] : 0) + 1;
                    up[i][j] = (i > 0 ? up[i-1][j] : 0) + 1;
                }
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) {
                int k = Math.min(left[i][j], up[i][j]);
                while (k > 0) {
                    if (left[i-k+1][j] >= k && up[i][j-k+1] >= k) {
                        ans = Math.max(ans, k*k);
                        break;
                    }
                    k--;
                }
            }
        return ans;
    }
}
 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

class Solution {
    fun largest1BorderedSquare(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid[0].size
        val left = Array(m) { IntArray(n) }
        val up = Array(m) { IntArray(n) }
        var ans = 0
        for (i in 0 until m)
            for (j in 0 until n)
                if (grid[i][j] == 1) {
                    left[i][j] = if (j > 0) left[i][j-1] + 1 else 1
                    up[i][j] = if (i > 0) up[i-1][j] + 1 else 1
                }
        for (i in 0 until m)
            for (j in 0 until n) {
                var k = minOf(left[i][j], up[i][j])
                while (k > 0) {
                    if (left[i-k+1][j] >= k && up[i][j-k+1] >= k) {
                        ans = maxOf(ans, k*k)
                        break
                    }
                    k--
                }
            }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def largest1BorderedSquare(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        left = [[0]*n for _ in range(m)]
        up = [[0]*n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    left[i][j] = (left[i][j-1] if j else 0) + 1
                    up[i][j] = (up[i-1][j] if i else 0) + 1
        ans = 0
        for i in range(m):
            for j in range(n):
                k = min(left[i][j], up[i][j])
                while k > 0:
                    if left[i-k+1][j] >= k and up[i][j-k+1] >= k:
                        ans = max(ans, k*k)
                        break
                    k -= 1
        return ans
 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
30

impl Solution {
    pub fn largest1_bordered_square(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut left = vec![vec![0; n]; m];
        let mut up = vec![vec![0; n]; m];
        for i in 0..m {
            for j in 0..n {
                if grid[i][j] == 1 {
                    left[i][j] = if j > 0 { left[i][j-1] + 1 } else { 1 };
                    up[i][j] = if i > 0 { up[i-1][j] + 1 } else { 1 };
                }
            }
        }
        let mut ans = 0;
        for i in 0..m {
            for j in 0..n {
                let mut k = left[i][j].min(up[i][j]);
                while k > 0 {
                    if left[i-k+1][j] >= k && up[i][j-k+1] >= k {
                        ans = ans.max(k*k);
                        break;
                    }
                    k -= 1;
                }
            }
        }
        ans
    }
}
 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

class Solution {
    largest1BorderedSquare(grid: number[][]): number {
        const m = grid.length, n = grid[0].length
        const left = Array.from({length: m}, () => Array(n).fill(0))
        const up = Array.from({length: m}, () => Array(n).fill(0))
        for (let i = 0; i < m; ++i)
            for (let j = 0; j < n; ++j)
                if (grid[i][j]) {
                    left[i][j] = (j ? left[i][j-1] : 0) + 1
                    up[i][j] = (i ? up[i-1][j] : 0) + 1
                }
        let ans = 0
        for (let i = 0; i < m; ++i)
            for (let j = 0; j < n; ++j) {
                let k = Math.min(left[i][j], up[i][j])
                while (k > 0) {
                    if (left[i-k+1][j] >= k && up[i][j-k+1] >= k) {
                        ans = Math.max(ans, k*k)
                        break
                    }
                    k--
                }
            }
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(m*n*min(m,n)), where m and n are grid dimensions. For each cell, we may check up to min(m, n) square sizes.
  • 🧺 Space complexity: O(m*n), for the DP tables.