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] is 0 or 1Problem 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.
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.
The 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.
Python
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.
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.
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.
JavaScript
Time Complexity: O(n*m*min(n,m)).
Space Complexity: O(n*m) to store the cumulative sums.
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.
The solution iterates over each cell in the grid and uses nested loops to expand potential squares. It checks all borders of each potential square for a continuous sequence of 1s.
Time Complexity: O(N^4) due to nested loops for checking each potential square.
Space Complexity: O(1) as no additional data structures are used.
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.
This C solution uses dynamic programming matrices dpLeft and dpUp to store the count of consecutive 1s to the left and upwards. For each grid[i][j], the largest possible square which has all 1s bordering is checked using its minimum value of those arrays, resulting in an efficient check.
Time Complexity: O(N^3) due to precomputation and checking needed for potential square dimensions at each cell.
Space Complexity: O(N*M) for dpLeft and dpUp.
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.
| 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) due to nested loops for checking each potential square. Space Complexity: O(1) as no additional data structures are used. |
| Dynamic Programming Approach | Time Complexity: O(N^3) due to precomputation and checking needed for potential square dimensions at each cell. Space Complexity: O(N*M) for |
| Prefix Sum + Enumeration | — |
| 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 |
Разбор задачи 1139 leetcode.com Largest 1-Bordered Square. Часть 2 • 3.5 задачи в неделю • 5,246 views views
Watch 9 more video solutions →Practice Largest 1-Bordered Square with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor