Largest 1-Bordered Square

medium dynamic programming matrix prefix sum

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 (the interior cells may be anything). If no such square exists, return 0.

Inputgrid = [[1,1,1],[1,0,1],[1,1,1]]

Output9

The whole 3×3 square has all-1 borders, so its area 3 × 3 = 9 is returned.

grid (rows separated by ; , cells by ,)

def largest1BorderedSquare(grid):
    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] == 1:
                down[i][j] = 1 + (down[i + 1][j] if i + 1 < m else 0)
                right[i][j] = 1 + (right[i][j + 1] if j + 1 < n else 0)
    best = 0
    for i in range(m):
        for j in range(n):
            side = min(down[i][j], right[i][j])
            while side > best:
                if (right[i + side - 1][j] >= side and
                        down[i][j + side - 1] >= side):
                    best = side
                side -= 1
    return best * best

function largest1BorderedSquare(grid) {
  const m = grid.length, n = grid[0].length;
  const down = Array.from({ length: m }, () => Array(n).fill(0));
  const right = Array.from({ length: m }, () => Array(n).fill(0));
  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      if (grid[i][j] === 1) {
        down[i][j] = 1 + (i + 1 < m ? down[i + 1][j] : 0);
        right[i][j] = 1 + (j + 1 < n ? right[i][j + 1] : 0);
      }
    }
  }
  let best = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      let side = Math.min(down[i][j], right[i][j]);
      while (side > best) {
        if (right[i + side - 1][j] >= side && down[i][j + side - 1] >= side) best = side;
        side--;
      }
    }
  }
  return best * best;
}

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

int largest1BorderedSquare(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> down(m, vector<int>(n, 0)), right(m, vector<int>(n, 0));
    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            if (grid[i][j] == 1) {
                down[i][j] = 1 + (i + 1 < m ? down[i + 1][j] : 0);
                right[i][j] = 1 + (j + 1 < n ? right[i][j + 1] : 0);
            }
        }
    }
    int best = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int side = min(down[i][j], right[i][j]);
            while (side > best) {
                if (right[i + side - 1][j] >= side && down[i][j + side - 1] >= side) best = side;
                side--;
            }
        }
    }
    return best * best;
}

Explanation

We want the biggest square in a 0/1 grid whose four edges are all 1s (the inside can be anything). The smart move is to first measure runs of 1s, then check candidate squares quickly.

We build two helper grids: down[i][j] = how many consecutive 1s go downward starting at (i,j), and right[i][j] = how many consecutive 1s go rightward. Each is filled in one bottom-right-to-top-left pass by adding 1 to the neighbor's count.

Then we treat each cell as a square's top-left corner. The largest side it could support is min(down, right). We try sizes from big to small: a square of side s is valid only if its bottom edge and right edge also have at least s ones, checked with right[i+s-1][j] and down[i][j+s-1].

We keep the best valid side and return its area, best*best.

Example: for the 3×3 grid [[1,1,1],[1,0,1],[1,1,1]] the whole border is 1, so side 3 works and the answer is 9.

Time: O(m · n · min(m, n)) Space: O(m · n)