Largest 1-Bordered Square

Medium
1558.

Largest 1-Bordered Square

Largest 1-Bordered Square is a medium coding problem on arrays, dynamic programming and matrix, asked in Google and Samsung interviews.

You are given a binary matrix grid of 0s and 1s. Find the largest square sub-grid whose border — its top row, bottom row, left column and right column — consists entirely of 1s. The cells strictly inside the border may hold anything.

Return the number of cells in that square (its side length squared), or 0 if the grid has no 1 at all.

Example 1

Input
grid = [[1,1,1,0],[1,0,1,1],[1,1,1,1]]
Output
9
Explanation
The 3 × 3 square in the first three columns has a border of 1s; the 0 in its centre does not matter.

Example 2

Input
grid = [[0,1],[1,1]]
Output
1
Explanation
The 2 × 2 square fails at its top-left corner, so the best is a single cell.

Example 3

Input
grid = [[0,0],[0,0]]
Output
0

Constraints

  • 1 <= grid.length <= 100
  • 1 <= grid[0].length <= 100
  • grid[i][j] is 0 or 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var largest1BorderedSquare = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Largest 1-Bordered Square — Solution in Python, Java & C++

Largest 1-Bordered Square solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Largest 1-Bordered Square is a medium coding problem on arrays, dynamic programming and matrix, asked in Google and Samsung interviews.

Problem statement

You are given a binary matrix grid of 0s and 1s. Find the largest square sub-grid whose border — its top row, bottom row, left column and right column — consists entirely of 1s. The cells strictly inside the border may hold anything.

Return the number of cells in that square (its side length squared), or 0 if the grid has no 1 at all.

Example 1

Input: grid = [[1,1,1,0],[1,0,1,1],[1,1,1,1]]
Output: 9
Explanation: The 3 × 3 square in the first three columns has a border of 1s; the 0 in its centre does not matter.

Example 2

Input: grid = [[0,1],[1,1]]
Output: 1
Explanation: The 2 × 2 square fails at its top-left corner, so the best is a single cell.

Example 3

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

Constraints

  • 1 <= grid.length <= 100
  • 1 <= grid[0].length <= 100
  • grid[i][j] is 0 or 1

Hints for Largest 1-Bordered Square

  1. Hint 1

    A square of side k with bottom-right corner (i, j) needs four runs of at least k ones: leftwards and upwards from (i, j), upwards from (i, j-k+1) and leftwards from (i-k+1, j).

  2. Hint 2

    Precompute, for every cell, how many consecutive 1s end there going left and going up.

  3. Hint 3

    For each cell as a bottom-right corner, try sides from min(left, up) downwards and stop at the first side whose other two edges are long enough.

How to solve Largest 1-Bordered Square

With run-length tables left[i][j] (consecutive 1s ending at (i, j) along the row) and up[i][j] (along the column), each candidate square's border is verified in O(1).

Approach

  1. Scan the grid row by row. For a 1 at (i, j) set left[i][j] = left[i][j-1] + 1 and up[i][j] = up[i-1][j] + 1 (0 for a 0 cell).
  2. Treat (i, j) as the bottom-right corner. For k from min(left[i][j], up[i][j]) down to best + 1: the bottom and right edges are guaranteed; check the left edge up[i][j-k+1] >= k and the top edge left[i-k+1][j] >= k.
  3. On the first k that passes, record it as the new best side and stop trying smaller sides at this corner.
  4. Return best * best.

Why it works

A square's border is exactly four straight runs of 1s of length k meeting at its corners, and each run is checked by one table lookup at the run's far end. Every square is tried at its bottom-right corner, so the maximum is found.

Complexity

  • Time — O(m · n · min(m, n))
  • Space — O(m · n)

Pitfalls

  • The interior does not need to be 1s — only the border.
  • Return the area (side squared), not the side length.
  • A single 1 is already a valid 1 × 1 square.

Reference solution

Python

from typing import List

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

Java

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

C++

int largest1BorderedSquare(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size(), best = 0;
    vector<vector<int>> left(m, vector<int>(n, 0)), up(m, vector<int>(n, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 0) continue;
            left[i][j] = (j > 0 ? left[i][j - 1] : 0) + 1;
            up[i][j] = (i > 0 ? up[i - 1][j] : 0) + 1;
            for (int k = min(left[i][j], up[i][j]); k > best; k--) {
                if (up[i][j - k + 1] >= k && left[i - k + 1][j] >= k) { best = k; break; }
            }
        }
    }
    return best * best;
}

JavaScript

var largest1BorderedSquare = function(grid) {
    var m = grid.length, n = grid[0].length, best = 0;
    var left = [], up = [];
    for (var r = 0; r < m; r++) { left.push(new Array(n).fill(0)); up.push(new Array(n).fill(0)); }
    for (var i = 0; i < m; i++) {
        for (var j = 0; j < n; j++) {
            if (grid[i][j] === 0) continue;
            left[i][j] = (j > 0 ? left[i][j - 1] : 0) + 1;
            up[i][j] = (i > 0 ? up[i - 1][j] : 0) + 1;
            for (var k = Math.min(left[i][j], up[i][j]); k > best; k--) {
                if (up[i][j - k + 1] >= k && left[i - k + 1][j] >= k) { best = k; break; }
            }
        }
    }
    return best * best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming