Largest 1-Bordered Square

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

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

Method 1 — Brute force (check every square)

Intuition

Check every possible square (top-left and size). For each candidate square, verify all four borders contain only 1s.

Approach

• Iterate over all possible top-left coordinates r,c.
• For each, iterate possible size from 1 up to min(n-r, m-c).
• For each candidate square, scan the top row, bottom row, left column and right column; if all are 1, update ans = max(ans, size*size).
• This checks all squares and validates borders explicitly.

Code

C++

class Solution {
 public:
  int largest1BorderedSquare(std::vector<std::vector<int>>& mat) {
    int n = mat.size();
    int m = mat[0].size();
    int ans = 0;
    for (int r = 0; r < n; ++r) {
      for (int c = 0; c < m; ++c) {
        for (int sz = 1; r + sz <= n && c + sz <= m; ++sz) {
          bool ok = true;
          int r2 = r + sz - 1;
          int c2 = c + sz - 1;
          for (int j = c; j <= c2 && ok; ++j) {
            if (!mat[r][j] || !mat[r2][j]) ok = false;
          }
          for (int i = r; i <= r2 && ok; ++i) {
            if (!mat[i][c] || !mat[i][c2]) ok = false;
          }
          if (ok) ans = std::max(ans, sz * sz);
        }
      }
    }
    return ans;
  }
};

Go

package main

func largest1BorderedSquare(mat [][]int) int {
    n := len(mat)
    m := len(mat[0])
    ans := 0
    for r := 0; r < n; r++ {
        for c := 0; c < m; c++ {
            for sz := 1; r+sz <= n && c+sz <= m; sz++ {
                ok := true
                r2 := r + sz - 1
                c2 := c + sz - 1
                for j := c; j <= c2 && ok; j++ {
                    if mat[r][j] == 0 || mat[r2][j] == 0 { ok = false }
                }
                for i := r; i <= r2 && ok; i++ {
                    if mat[i][c] == 0 || mat[i][c2] == 0 { ok = false }
                }
                if ok && sz*sz > ans { ans = sz * sz }
            }
        }
    }
    return ans
}

Java

class Solution {
  public int largest1BorderedSquare(int[][] mat) {
    int n = mat.length, m = mat[0].length;
    int ans = 0;
    for (int r = 0; r < n; ++r) {
      for (int c = 0; c < m; ++c) {
        for (int sz = 1; r + sz <= n && c + sz <= m; ++sz) {
          boolean ok = true;
          int r2 = r + sz - 1, c2 = c + sz - 1;
          for (int j = c; j <= c2 && ok; ++j) {
            if (mat[r][j] == 0 || mat[r2][j] == 0) ok = false;
          }
          for (int i = r; i <= r2 && ok; ++i) {
            if (mat[i][c] == 0 || mat[i][c2] == 0) ok = false;
          }
          if (ok) ans = Math.max(ans, sz * sz);
        }
      }
    }
    return ans;
  }
}

Python

class Solution:
    def largest1BorderedSquare(self, mat: list[list[int]]) -> int:
        n = len(mat)
        m = len(mat[0])
        ans = 0
        for r in range(n):
            for c in range(m):
                sz = 1
                while r + sz <= n and c + sz <= m:
                    ok = True
                    r2 = r + sz - 1
                    c2 = c + sz - 1
                    for j in range(c, c2 + 1):
                        if mat[r][j] == 0 or mat[r2][j] == 0:
                            ok = False
                            break
                    for i in range(r, r2 + 1) and ok:
                        if mat[i][c] == 0 or mat[i][c2] == 0:
                            ok = False
                            break
                    if ok:
                        ans = max(ans, sz * sz)
                    sz += 1
        return ans

Complexity

• ⏰ Time complexity: O(n^3) — three nested loops over rows, columns and sizes and O(sz) border checks, worst-case accumulates to cubic; reasoning above.
• 🧺 Space complexity: O(1) — only constant extra variables.

Method 2 – 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

C++

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;
    }
};

Go

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
}

Java

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;
    }
}

Kotlin

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
    }
}

Python

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

Rust

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
    }
}

TypeScript

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.