Largest 1-Bordered Square solution and explanation
9 more videos on this problem
Разбор задачи 1139 leetcode.com Largest 1-Bordered Square. Часть 23.5 задачи в неделю · 1:22:20 · 5K views
LeetCode 1139. Largest 1-Bordered Square Explanation and Solutionhappygirlzt · 11:20 · 3K views
1139. Largest 1 Bordered Square (Weekly Contest 147)Kelvin Chandra · 7:52 · 3K views
Leetcode 1139. Largest 1-Bordered SquareElite Code · 25:37 · 1K views
Разбор задачи 1139 leetcode.com Largest 1-Bordered Square3.5 задачи в неделю · 1:32:21 · 1K views
LeetCode 1139. Largest 1-Bordered Square 中文解释 Chinese Versionhappygirlzt · 12:58 · 1K views
米开：LeetCode 1139. Largest 1-Bordered SquareM.C米开朗基罗 · 9:30 · 448 views
LeetCode 1139 Largest 1 Bordered Square | JavaHow we live in Texas · 7:36 · 118 views
Leetcode 1139Retriever · 4:15 · 37 views
LeetCode 1139: Largest 1-Bordered SquareAlitaCode · 28:22 · 31 views
The 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.
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 <= 1001 <= grid[0].length <= 100grid[i][j]is0or1
Approach overview
Problem Overview: You are given a binary matrix. The task is to find the area of the largest square whose four borders are entirely made of 1s. The inside of the square can contain anything, but every cell along the top, bottom, left, and right edges must be 1.
Approach 1: Brute Force Approach (O(n4 * n) time, O(1) space)
The most direct solution checks every possible square in the grid. Iterate over all cells as the top‑left corner, try every possible side length, and verify whether the four borders contain only 1s. Border validation requires scanning the entire perimeter of the candidate square, which costs O(k) for side length k. Since there are O(n4) possible squares in an n x n grid, the overall runtime becomes O(n5) in the worst case. This method is useful for understanding the constraints and verifying correctness but becomes slow for larger matrices.
Approach 2: Prefix Sum Arrays (O(m * n * min(m,n)) time, O(m * n) space)
Prefix sums speed up border validation. Build prefix sums for rows and columns so you can quickly count the number of 1s in any horizontal or vertical segment. For each candidate square, check the top, bottom, left, and right edges using constant-time prefix sum queries. Instead of scanning each border cell-by-cell, you compare the segment length with the number of 1s returned by the prefix query. If they match, the entire edge is valid. This reduces border checks to O(1), bringing the total runtime to roughly O(m * n * min(m,n)). This approach fits naturally with problems involving cumulative counts in Array and Matrix processing.
Approach 3: Dynamic Programming (O(m * n * min(m,n)) time, O(m * n) space)
A more common optimization precomputes how many consecutive 1s extend leftward and upward from each cell. Maintain two DP tables: left[i][j] for horizontal streaks and up[i][j] for vertical streaks. For a cell acting as the bottom-right corner of a square, the maximum possible side length equals min(left[i][j], up[i][j]). Try side lengths from largest to smallest and verify the opposite edges using the DP values: check if the top border and left border also have sufficient consecutive 1s. Each check is constant time, making the algorithm efficient while scanning the grid once. This technique is common in Dynamic Programming problems on grids.
Recommended for interviews: The dynamic programming solution is the expected answer. It demonstrates awareness of preprocessing and constant-time border checks while keeping the complexity manageable at O(m * n * min(m,n)). Mentioning the brute force approach first shows you understand the naive search space, then optimizing with DP highlights problem‑solving depth.
Approach 1: Prefix Sum Arrays
This approach leverages prefix sum arrays to efficiently calculate the number of contiguous 1s horizontally and vertically for each cell. This optimization allows us to validate potential squares in constant time.
For each potential top-left corner of the square, increase the side length as long as all four borders are comprised entirely of 1s, using the helper arrays to check borders efficiently.
def largest1BorderedSquare(grid):
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
max_side = 0
hor = [[0] * (cols + 1) for _ in range(rows + 1)]
ver = [[0] * (cols + 1) for _ in range(rows + 1)]
for r in range(1, rows + 1):
for c in range(1, cols + 1):
if grid[r-1][c-1] == 1:
hor[r][c] = hor[r][c-1] + 1
ver[r][c] = ver[r-1][c] + 1
for r in range(1, rows + 1):
for c in range(1, cols + 1):
side_len = min(hor[r][c], ver[r][c])
while side_len > max_side:
if hor[r-side_len+1][c] >= side_len and ver[r][c-side_len+1] >= side_len:
max_side = side_len
side_len -= 1
return max_side ** 2The solution maintains two auxiliary matrices, hor and ver, where hor[r][c] represents the number of consecutive 1s ending at (r,c) horizontally, and ver[r][c] counts them vertically. For each cell, it attempts to form the largest possible square and checks whether the necessary borders have sufficient 1s.
Time Complexity: O(n*m*min(n,m)) due to the nested loop structure.
Space Complexity: O(n*m) for the hor and ver arrays.
Approach 2: Dynamic Programming
This approach employs dynamic programming to track the maximum side length of squares that can be formed using 1-filled borders. Utilize a 2D DP array to store the largest possible square ending at each point, beginning from each potential bottom-right corner and working backwards.
function largest1BorderedSquare(grid) {
if (!grid.length || !grid[0].length) return 0;
let rows = grid.length, cols = grid[0].length;
let maxSide = 0;
const horiz = Array.from({ length: rows + 1 }, () => Array(cols + 1).fill(0));
const vert = Array.from({ length: rows + 1 }, () => Array(cols + 1).fill(0));
for (let r = 1; r <= rows; r++) {
for (let c = 1; c <= cols; c++) {
if (grid[r - 1][c - 1] === 1) {
horiz[r][c] = horiz[r][c - 1] + 1;
vert[r][c] = vert[r - 1][c] + 1;
}
}
}
for (let r = 1; r <= rows; r++) {
for (let c = 1; c <= cols; c++) {
let sideLength = Math.min(horiz[r][c], vert[r][c]);
while (sideLength > maxSide) {
if (horiz[r - sideLength + 1][c] >= sideLength && vert[r][c - sideLength + 1] >= sideLength) {
maxSide = sideLength;
}
sideLength--;
}
}
}
return maxSide * maxSide;
}This JavaScript solution maintains horizontal and vertical cumulative sums similar to the Python solution and checks for the maximum squares possible by examining borders of decreasing lengths, updating the maximum side when a larger square is found.
Time Complexity: O(n*m*min(n,m)).
Space Complexity: O(n*m) to store the cumulative sums.
Approach 3: Brute Force Approach
This approach involves checking all possible squares with the top-left corner at any point in the grid. For each potential square, verify if all sides of the boundary consist of 1s. This verification process has an O(N^4) complexity which might be inefficient for larger grids.
def largest1BorderedSquare(grid):
n = len(grid)
if n == 0:
return 0
m = len(grid[0])
max_side = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
for k in range(1, min(n - i, m - j)):
is_border = True
for l in range(k + 1):
if grid[i + l][j] == 0 or grid[i][j + l] == 0 or \
grid[i + k][j + l] == 0 or grid[i + l][j + k] == 0:
is_border = False
break
if is_border:
max_side = max(max_side, k + 1)
return max_side * max_sideclass Solution {
public int largest1BorderedSquare(int[][] grid) {
int n = grid.length;
if (n == 0) return 0;
int m = grid[0].length;
int maxSide = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 1) {
for (int k = 1; i + k < n && j + k < m; ++k) {
boolean isBorder = true;
for (int l = 0; l <= k; ++l) {
if (grid[i + l][j] == 0 || grid[i][j + l] == 0 ||
grid[i + k][j + l] == 0 || grid[i + l][j + k] == 0) {
isBorder = false;
break;
}
}
if (isBorder) {
maxSide = Math.max(maxSide, k + 1);
}
}
}
}
}
return maxSide * maxSide;
}
}#include <vector>
using namespace std;
int largest1BorderedSquare(vector<vector<int>>& grid) {
int n = grid.size();
if (n == 0) return 0;
int m = grid[0].size();
int maxSide = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 1) {
for (int k = 1; i + k < n && j + k < m; ++k) {
bool isBorder = true;
for (int l = 0; l <= k; ++l) {
if (grid[i + l][j] == 0 || grid[i][j + l] == 0 ||
grid[i + k][j + l] == 0 || grid[i + l][j + k] == 0) {
isBorder = false;
break;
}
}
if (isBorder) {
maxSide = max(maxSide, k + 1);
}
}
}
}
}
return maxSide * maxSide;
}var largest1BorderedSquare = function(grid) {
let n = grid.length;
if (n === 0) return 0;
let m = grid[0].length;
let maxSide = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (grid[i][j] === 1) {
for (let k = 1; i + k < n && j + k < m; k++) {
let isBorder = true;
for (let l = 0; l <= k; l++) {
if (grid[i + l][j] === 0 || grid[i][j + l] === 0 ||
grid[i + k][j + l] === 0 || grid[i + l][j + k] === 0) {
isBorder = false;
break;
}
}
if (isBorder) {
maxSide = Math.max(maxSide, k + 1);
}
}
}
}
}
return maxSide * maxSide;
};#include <stdbool.h>
#include <string.h>
int min(int a, int b) {
return a < b ? a : b;
}
int largest1BorderedSquare(int** grid, int gridSize, int* gridColSize) {
int maxSide = 0;
for (int i = 0; i < gridSize; ++i) {
for (int j = 0; j < gridColSize[i]; ++j) {
if (grid[i][j] == 1) {
for (int k = 1; i + k < gridSize && j + k < gridColSize[i]; ++k) {
bool isBorder = true;
for (int l = 0; l <= k; ++l) {
if (grid[i + l][j] == 0 || grid[i][j + l] == 0 ||
grid[i + k][j + l] == 0 || grid[i + l][j + k] == 0) {
isBorder = false;
break;
}
}
if (isBorder) {
maxSide = max(maxSide, k + 1);
}
}
}
}
}
return maxSide * maxSide;
}public class Solution {
public int Largest1BorderedSquare(int[][] grid) {
int n = grid.Length;
if (n == 0) return 0;
int m = grid[0].Length;
int maxSide = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 1) {
for (int k = 1; i + k < n && j + k < m; ++k) {
bool isBorder = true;
for (int l = 0; l <= k; ++l) {
if (grid[i + l][j] == 0 || grid[i][j + l] == 0 ||
grid[i + k][j + l] == 0 || grid[i + l][j + k] == 0) {
isBorder = false;
break;
}
}
if (isBorder) {
maxSide = Math.Max(maxSide, k + 1);
}
}
}
}
}
return maxSide * maxSide;
}
}The Python solution follows the same logic as the other languages, iterating through each cell, checking borders for all 1s, and tracking the largest valid square.
Time Complexity: O(N^4), stemming from the need to examine all candidate squares.
Space Complexity: O(1).
Approach 4: Dynamic Programming Approach
This method uses dynamic programming to precompute the number of continuous 1s to the left and above each cell. This allows for efficient verification if a square with a certain size can be made starting from any point.
def largest1BorderedSquare(grid):
if not grid:
return 0
n, m = len(grid), len(grid[0])
dpLeft = [[0] * m for _ in range(n)]
dpUp = [[0] * m for _ in range(n)]
max_side = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
dpLeft[i][j] = (dpLeft[i][j-1] if j > 0 else 0) + 1
dpUp[i][j] = (dpUp[i-1][j] if i > 0 else 0) + 1
side = min(dpLeft[i][j], dpUp[i][j])
while side > max_side:
if dpLeft[i-side+1][j] >= side and dpUp[i][j-side+1] >= side:
max_side = side
break
side -= 1
return max_side * max_sideclass Solution {
public int largest1BorderedSquare(int[][] grid) {
int n = grid.length;
if (n == 0) return 0;
int m = grid[0].length;
int[][] dpLeft = new int[n][m];
int[][] dpUp = new int[n][m];
int maxSide = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 1) {
dpLeft[i][j] = (j == 0 ? 0 : dpLeft[i][j-1]) + 1;
dpUp[i][j] = (i == 0 ? 0 : dpUp[i-1][j]) + 1;
int side = Math.min(dpLeft[i][j], dpUp[i][j]);
while (side > maxSide) {
if (dpLeft[i-side+1][j] >= side && dpUp[i][j-side+1] >= side) {
maxSide = side;
break;
}
side--;
}
}
}
}
return maxSide * maxSide;
}
}#include <vector>
#include <algorithm>
using namespace std;
int largest1BorderedSquare(vector<vector<int>>& grid) {
int n = grid.size();
if (n == 0) return 0;
int m = grid[0].size();
vector<vector<int>> dpLeft(n, vector<int>(m, 0));
vector<vector<int>> dpUp(n, vector<int>(m, 0));
int maxSide = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 1) {
dpLeft[i][j] = (j == 0 ? 0 : dpLeft[i][j-1]) + 1;
dpUp[i][j] = (i == 0 ? 0 : dpUp[i-1][j]) + 1;
int side = min(dpLeft[i][j], dpUp[i][j]);
while (side > maxSide) {
if (dpLeft[i-side+1][j] >= side && dpUp[i][j-side+1] >= side) {
maxSide = side;
break;
}
side--;
}
}
}
}
return maxSide * maxSide;
}var largest1BorderedSquare = function(grid) {
let n = grid.length;
if (n === 0) return 0;
let m = grid[0].length;
let dpLeft = Array.from({length: n}, () => Array(m).fill(0));
let dpUp = Array.from({length: n}, () => Array(m).fill(0));
let maxSide = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (grid[i][j] === 1) {
dpLeft[i][j] = (j === 0 ? 0 : dpLeft[i][j-1]) + 1;
dpUp[i][j] = (i === 0 ? 0 : dpUp[i-1][j]) + 1;
let side = Math.min(dpLeft[i][j], dpUp[i][j]);
while (side > maxSide) {
if (dpLeft[i-side+1][j] >= side && dpUp[i][j-side+1] >= side) {
maxSide = side;
break;
}
side--;
}
}
}
}
return maxSide * maxSide;
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int max(int a, int b) {
return a > b ? a : b;
}
int largest1BorderedSquare(int** grid, int gridSize, int* gridColSize) {
int n = gridSize;
if (n == 0) return 0;
int m = gridColSize[0];
int maxSide = 0;
int **dpLeft = (int**)malloc(n * sizeof(int*));
int **dpUp = (int**)malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) {
dpLeft[i] = (int*)malloc(m * sizeof(int));
dpUp[i] = (int*)malloc(m * sizeof(int));
memset(dpLeft[i], 0, m * sizeof(int));
memset(dpUp[i], 0, m * sizeof(int));
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1) {
dpLeft[i][j] = (j == 0 ? 0 : dpLeft[i][j-1]) + 1;
dpUp[i][j] = (i == 0 ? 0 : dpUp[i-1][j]) + 1;
int side = min(dpLeft[i][j], dpUp[i][j]);
while (side > maxSide) {
if (dpLeft[i-side+1][j] >= side && dpUp[i][j-side+1] >= side) {
maxSide = side;
break;
}
side--;
}
}
}
}
for (int i = 0; i < n; i++) {
free(dpLeft[i]);
free(dpUp[i]);
}
free(dpLeft);
free(dpUp);
return maxSide * maxSide;
}public class Solution {
public int Largest1BorderedSquare(int[][] grid) {
int n = grid.Length;
if (n == 0) return 0;
int m = grid[0].Length;
int[,] dpLeft = new int[n, m];
int[,] dpUp = new int[n, m];
int maxSide = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 1) {
dpLeft[i, j] = (j == 0 ? 0 : dpLeft[i, j-1]) + 1;
dpUp[i, j] = (i == 0 ? 0 : dpUp[i-1, j]) + 1;
int side = Math.Min(dpLeft[i, j], dpUp[i, j]);
while (side > maxSide) {
if (dpLeft[i-side+1, j] >= side && dpUp[i, j-side+1] >= side) {
maxSide = side;
break;
}
side--;
}
}
}
}
return maxSide * maxSide;
}
}The approach relies on dynamic programming arrays in Python to track sequences of 1s horizontally and vertically, allowing rapid checks for the maximum valid bordered square from each cell.
Time Complexity: O(N^3) resulting from evaluating potential squares.
Space Complexity: O(N*M).
Approach 5: Prefix Sum + Enumeration
We can use the prefix sum method to preprocess the number of consecutive 1s down and to the right of each position, denoted as down[i][j] and right[i][j].
Then we enumerate the side length k of the square, starting from the largest side length. Then we enumerate the upper left corner position (i, j) of the square. If it meets the condition, we can return k^2.
The time complexity is O(m times n times min(m, n)), and the space complexity is O(m times n). Here, m and n are the number of rows and columns of the grid, respectively.
func largest1BorderedSquare(grid [][]int) int {
m, n := len(grid), len(grid[0])
down := make([][]int, m)
right := make([][]int, m)
for i := range down {
down[i] = make([]int, n)
right[i] = make([]int, n)
}
for i := m - 1; i >= 0; i-- {
for j := n - 1; j >= 0; j-- {
if grid[i][j] == 1 {
down[i][j], right[i][j] = 1, 1
if i+1 < m {
down[i][j] += down[i+1][j]
}
if j+1 < n {
right[i][j] += right[i][j+1]
}
}
}
}
for k := min(m, n); k > 0; k-- {
for i := 0; i <= m-k; i++ {
for j := 0; j <= n-k; j++ {
if down[i][j] >= k && right[i][j] >= k && right[i+k-1][j] >= k && down[i][j+k-1] >= k {
return k * k
}
}
}
}
return 0
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix Sum Arrays | Time Complexity: O(n*m*min(n,m)) due to the nested loop structure. |
| Dynamic Programming | Time Complexity: O(n*m*min(n,m)). |
| Brute Force Approach | Time Complexity: O(N^4), stemming from the need to examine all candidate squares. Space Complexity: O(1). |
| Dynamic Programming Approach | Time Complexity: O(N^3) resulting from evaluating potential squares. Space Complexity: O(N*M). |
| Prefix Sum + Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n^5) | O(1) | Good for conceptual understanding or very small matrices |
| Prefix Sum Arrays | O(m * n * min(m,n)) | O(m * n) | When fast border validation using cumulative sums is preferred |
| Dynamic Programming (left/up streaks) | O(m * n * min(m,n)) | O(m * n) | Most common interview solution for grid DP problems |
Frequently asked questions
Is Largest 1-Bordered Square easy or hard?
Largest 1-Bordered Square is classified as a Medium difficulty problem. The challenge comes from recognizing that brute force border checks are too slow and that preprocessing with dynamic programming or prefix sums enables efficient validation.
Largest 1-Bordered Square Python/Java solution
Python solutions often use prefix sum arrays or DP tables to check borders efficiently. Java and C++ implementations commonly use two DP matrices to store consecutive left and upward 1 counts, achieving O(m * n * min(m,n)) time complexity.
How to solve Largest 1-Bordered Square in O(n)?
An O(n) solution is not possible because the algorithm must inspect most cells of the matrix. The best known complexity is O(m * n * min(m,n)), achieved by preprocessing consecutive 1 counts or prefix sums so border checks run in constant time.
What is the best approach for Largest 1-Bordered Square?
Dynamic programming with precomputed horizontal and vertical streaks of 1s is the most effective approach. Two DP tables track consecutive 1s to the left and upward for each cell. This allows constant‑time border validation for candidate squares and achieves O(m * n * min(m,n)) time with O(m * n) space.
Is Largest 1-Bordered Square asked at Google/Amazon/Meta?
Grid dynamic programming problems similar to Largest 1-Bordered Square appear in interviews at companies like Amazon, Google, and Meta. Variants involving largest squares, rectangles, or border validation are common in coding interviews.
What data structure is used in Largest 1-Bordered Square?
The problem primarily uses 2D arrays for dynamic programming or prefix sums. These structures store precomputed counts of consecutive 1s horizontally and vertically, enabling fast validation of square borders in a binary matrix.
What is the time complexity of Largest 1-Bordered Square?
The optimized dynamic programming and prefix sum approaches both run in O(m * n * min(m,n)) time for an m by n matrix. Each cell is processed once, and possible square sizes are checked efficiently using precomputed data structures.