Watch 10 video solutions for Largest 1-Bordered Square, a medium level problem involving Array, Dynamic Programming, Matrix. This walkthrough by 3.5 задачи в неделю has 5,246 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |