Square of Zeroes

Tags

Square of Zeroes

Category

Dynamic Programming

Difficulty

Very Hard

Problem Statement

Given an n x n matrix of 0s and 1s, determine whether there exists a square whose border is made entirely of 0s. The square does not need to be at the boundary of the matrix; it can be located anywhere. Return true if such a square exists with side length >= 2, false otherwise.

Intuition

Checking every possible square naively and verifying its border would take O(n^4) time (O(n^3) squares times O(n) to verify each border). We can precompute for every cell the number of consecutive zeroes going downward and to the right. With this information, verifying whether a given top-left corner can anchor a square of a certain size becomes an O(1) operation: check that the top-left corner has enough zeroes going right and down, and that the top-right and bottom-left corners have enough zeroes going down and right, respectively.

Approach

  1. Precompute prefix sums of consecutive zeroes:
    • Build zeroesBelow[i][j]: number of consecutive 0s starting at (i, j) going downward.
    • Build zeroesRight[i][j]: number of consecutive 0s starting at (i, j) going rightward.
    • Compute these by scanning from the bottom-right corner upward and leftward.
  2. Check all possible squares:
    • For each cell (r, c) as the potential top-left corner:
      • For each possible side length size from 2 to min(n - r, n - c):
        • Top-left (r, c): needs zeroesRight >= size and zeroesBelow >= size.
        • Top-right (r, c + size - 1): needs zeroesBelow >= size.
        • Bottom-left (r + size - 1, c): needs zeroesRight >= size.
        • If all conditions hold, a valid square of zeroes exists; return true.
  3. If no valid square is found, return false.

Pseudocode

function squareOfZeroes(matrix):
    n = length(matrix)

    // Precompute consecutive zeroes going down
    zeroesBelow = 2D array of size n x n
    for c from 0 to n-1:
        zeroesBelow[n-1][c] = (1 - matrix[n-1][c])
        for r from n-2 down to 0:
            if matrix[r][c] == 0:
                zeroesBelow[r][c] = zeroesBelow[r+1][c] + 1
            else:
                zeroesBelow[r][c] = 0

    // Precompute consecutive zeroes going right
    zeroesRight = 2D array of size n x n
    for r from 0 to n-1:
        zeroesRight[r][n-1] = (1 - matrix[r][n-1])
        for c from n-2 down to 0:
            if matrix[r][c] == 0:
                zeroesRight[r][c] = zeroesRight[r][c+1] + 1
            else:
                zeroesRight[r][c] = 0

    // Check all possible squares
    for r from 0 to n-1:
        for c from 0 to n-1:
            maxSize = min(n - r, n - c)
            for size from 2 to maxSize:
                topLeft  = zeroesRight[r][c] >= size and zeroesBelow[r][c] >= size
                topRight = zeroesBelow[r][c + size - 1] >= size
                botLeft  = zeroesRight[r + size - 1][c] >= size
                if topLeft and topRight and botLeft:
                    return true

    return false

Time & Space Complexity

  • Time: O(n^3). Precomputation is O(n^2). The triple-nested loop iterates over O(n^2) top-left corners and up to O(n) sizes each, giving O(n^3). Each check is O(1).
  • Space: O(n^2) for the two precomputed tables.

Key Insights

  • Precomputing "consecutive zeroes in a direction" transforms an O(n) border-check into an O(1) lookup.
  • Only four corner checks are needed to validate the entire border, because the consecutive-zero counts inherently cover all cells along the four sides.
  • The problem asks about the border only, not the interior of the square; interior values are irrelevant.
  • You can optimize further with binary search on size for each top-left corner, but the improvement is minor in practice.

Edge Cases

  • 1x1 matrix: No square of side length >= 2 is possible, return false.
  • 2x2 matrix of all zeroes: The entire matrix border is zeroes, return true.
  • Matrix of all ones: No border of zeroes exists, return false.
  • Matrix of all zeroes: The largest possible square (the entire matrix) qualifies.
  • Zeroes only on one row or column: Cannot form a 2D square border, return false.
  • Single zero surrounded by ones: Cannot form a square border of size >= 2.

Linked mentions