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.

Description Hints 2 Solution Video 1:22:20

1139. Largest 1-Bordered Square

Medium52.7% acceptance4 companies

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 <= 100
1 <= grid[0].length <= 100
grid[i][j] is 0 or 1

Asked at 4 companies

Samsung Zs Associates Amazon Uber

Topics

Hints open one at a time

Hint 1

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.

Hint 2

Now for each square ( O(N^3) ), we can evaluate whether that square is 1-bordered in O(1).

1:22:20

Still stuck?Read 5 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[[1,1,1],[1,0,1],[1,1,1]]

Input

[[1,1,0,0]]

Your code is saved on this device.Solution