Largest 1 bordered square

Array Dynamic Programming Matrix

52.0% acceptance

Feb 25, 2026

768

118

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

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