Largest X Bordered Square
Given a binary matrix of 0s and 1s, find the largest square submatrix whose entire border, all four edges, is made up only of 1s. The interior cells may hold either value.
Do this lesson first: longest common subsequenceExample input
[[1, 1, 1], [1, 0, 1], [1, 1, 1]]; 1 means X (marked), 0 means unmarked.
Expected output
3 (side length; area would be 9)
Work through the example
X describes a marked cell, not an X-shaped diagonal. The outer three-by-three square has marked cells along its entire top, bottom, left, and right borders. The center may be 0. At bottom-right (2, 2), left[2][2] = 3 and up[2][2] = 3 certify the bottom and right edges. left[0][2] = 3 certifies the top; up[2][0] = 3 certifies the left. All four runs reach 3, so a side of 3 is valid, and no larger square fits this matrix.
Break it down
Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.
The code, the trap, the variations
- 1
function largestBorderedSquare(matrix) { - 2
const rows = matrix.length; - 3
const cols = matrix[0]?.length ?? 0; - 4
for (const row of matrix) { - 5
if (row.length !== cols || row.some((cell) => cell !== 0 && cell !== 1)) { - 6
throw new RangeError("Expected a rectangular matrix containing only 0 and 1."); - 7
} - 8
} - 9
if (rows === 0 || cols === 0) return 0; - 10
const left = Array.from({ length: rows }, () => Array(cols).fill(0)); - 11
const up = Array.from({ length: rows }, () => Array(cols).fill(0)); - 12
let best = 0; - 13
for (let r = 0; r < rows; r++) { - 14
for (let c = 0; c < cols; c++) { - 15
if (matrix[r][c] === 0) continue; - 16
left[r][c] = 1 + (c > 0 ? left[r][c - 1] : 0); - 17
up[r][c] = 1 + (r > 0 ? up[r - 1][c] : 0); - 18
for (let side = Math.min(r + 1, c + 1); side > best; side--) { - 19
const top = r - side + 1; - 20
const firstCol = c - side + 1; - 21
if (left[r][c] >= side && up[r][c] >= side && - 22
left[top][c] >= side && up[r][firstCol] >= side) { - 23
best = side; - 24
break; - 25
} - 26
} - 27
} - 28
} - 29
return best; - 30
}
Where people go wrong
Checking only the bottom and right runs can accept a square with a broken top or left border. The filled-square recurrence 1 + min(top, left, diagonal) solves a different problem and rejects valid hollow squares. X means a marked cell, not diagonal arms. Return the side length here; multiply by itself only when a variant asks for area.
Return area instead of side length.
Keep the same search and return best * best. A three-by-three border has area 9 even if its interior is unmarked.
Require every cell inside the square to be marked.
Use the maximal filled-square recurrence: dp[r][c] = 1 + min(top, left, diagonal) at marked cells. Border runs alone no longer prove validity.
Return the square's location.
Save (top, firstCol) whenever best improves. Define how to break ties if several largest squares exist.
Section 12
Largest X bordered square: certify all four edges
Find the largest square whose border cells are all marked. Here X means a cell with value 1, not an X drawn along diagonals. The interior can contain zeros. This chapter returns the square's side length.
The idea to remember
- Store two directional runs: left[r][c] is the consecutive marked length ending horizontally at a cell; up[r][c] is the consecutive marked length ending vertically there.
- At a 1, extend left from the previous column and up from the previous row, adding 1. At a 0, both run lengths are 0. Missing predecessors contribute 0.
- For a square of side s ending at (r, c), top = r - s + 1 and firstCol = c - s + 1. Check left[r][c], up[r][c], left[top][c], and up[r][firstCol] are each at least s. They certify bottom, right, top, and left respectively.
- Read row by row from left to right. Try candidate sides downward and stop after finding a valid side at a corner. Skip sizes that cannot beat the best answer, but keep trying smaller sizes after a large candidate fails.
- A hollow square is valid, so the filled-square recurrence cannot replace the four border checks. The answer is a side length; area is its square.
- Worst-case time is O(rows * cols * min(rows, cols)); the two run tables use O(rows * cols) space. Empty and all-zero inputs return 0.
Work through one example
[[1, 1, 1], [1, 0, 1], [1, 1, 1]]
For bottom-right (2, 2) and side 3, the bottom, right, top, and left runs all have length 3. The center 0 is not on an edge and does not invalidate the square.
Largest side length: 3. Its area is 9.
Test your reasoning
Choose an answer for each question. You can try again after a hint.
0 / 2 answered correctly
Recall before you reveal
Say the answer to yourself, then reveal it. Use Previous and Next to move through this section.
Card 1 of 3 ยท 0 / 3 reviewed
Check your understanding
1. For [[1, 1, 1], [1, 0, 1], [1, 1, 1]], what should this side-length function return?
- 1, because the center is 0
- 2, because only filled squares count
- 3, because all four outer edges are marked
- 9, because the square covers nine positions
2. At bottom-right (2, 2) of [[1, 0, 1], [1, 1, 1], [1, 1, 1]], left[2][2] and up[2][2] are both 3. Why must the candidate of side 3 still be rejected?
- Its interior contains a 0
- Its top run left[0][2] is only 1
- The bottom row has too many marked cells
- Every square must start in row 1
Flashcards: cover the answer to recall it
What do left[r][c] and up[r][c] store?
Consecutive 1s ending at (r, c), horizontally and vertically. At a 1, add 1 to the preceding run; at a 0, reset to 0. Missing predecessors have length 0.
How do you certify side s ending at bottom-right (r, c)?
Set top = r - s + 1 and firstCol = c - s + 1. Require left[r][c] >= s for bottom, up[r][c] >= s for right, left[top][c] >= s for top, and up[r][firstCol] >= s for left.
Does a center 0 invalidate an X bordered square? What does the answer measure?
No. X means a marked border cell, and the interior is unrestricted. This function returns side length, so a hollow three-by-three square returns 3. Its area would be 9.
Quiz answer key
1. C. All four edges have length 3 and contain only 1s. The interior may be 0, so side 3 is valid. The answer is 3; 9 would be the area.
2. B. The top row [1, 0, 1] has a gap, giving left[0][2] = 1 < 3. A valid bottom and right edge do not certify the top or left. The smaller side-2 square in the bottom-right is valid, so the overall answer is 2.