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 1The key idea in #1139 Largest 1-Bordered Square is to efficiently verify whether a square in a binary matrix has borders made entirely of 1s. A brute force approach would check every possible square and validate its borders, but this leads to excessive repeated work.
A better strategy uses dynamic programming to precompute helpful information. For each cell, store how many consecutive 1s extend to the left and upward. With these values, you can quickly determine whether the four borders of a candidate square contain only 1s.
Iterate over each cell as a potential bottom-right corner and attempt the largest possible square size. Using the precomputed counts allows constant-time border validation for each candidate. This significantly reduces redundant checks compared to naive methods.
The approach typically runs in O(m × n × min(m, n)) time with O(m × n) additional space for the DP tables.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with border precomputation | O(m × n × min(m, n)) | O(m × n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
For each square, know how many ones are up, left, down, and right of this square. You can find it in O(N^2) using dynamic programming.
Now for each square ( O(N^3) ), we can evaluate whether that square is 1-bordered in O(1).
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, matrix and dynamic programming problems like Largest 1-Bordered Square are common in technical interviews. They test a candidate’s ability to preprocess data and optimize brute force solutions.
The optimal approach uses dynamic programming to precompute consecutive 1s extending left and upward from each cell. This allows constant-time verification of square borders, reducing repeated checks compared to brute force scanning.
Dynamic programming helps store previously computed information about consecutive 1s. This prevents repeated border checks and allows quick validation of potential squares during iteration.
A 2D dynamic programming matrix is typically used to store counts of consecutive 1s in horizontal and vertical directions. These helper matrices make it easy to validate whether a square's borders are all 1s.