Problem of The Day: Count Square Submatrices with All Ones

Problem Statement

Intuition

The problem requires us to find all possible square submatrices with all 1s in a given matrix. The first step is to understand that for any submatrix to be a square, the difference between its row and column ranges must match. Additionally, since all elements within the square must be 1, we need a way to validate each potential square region.

Approach

1. Identify matrix dimensions: First, get the number of rows and columns in the matrix, and determine the smallest dimension (n), which is the maximum possible size of any square submatrix.

2. Iterate through possible square sizes: Start with the smallest square size (1x1) and work up to n x n. For each size, iterate over all possible top-left corners of submatrices of that size.

3. Check submatrix validity: For each potential square, check all cells to ensure they contain only 1s by defining a helper method, is_valid_submatrix. This function returns True if all cells are 1s and False otherwise.

4. Count valid submatrices: If the submatrix is valid, increment the result counter. After iterating through all possible submatrices, return the total count.

Complexity

• Time complexity: The time complexity is approximately \(O(n^4)\), where n represents the length of the matrix’s longest dimension. This arises because:
  • We consider all possible submatrix sizes.
  • For each size, we iterate over the entire matrix to find valid squares, and each validation requires checking every cell within the square.
• Space complexity: \(O(1)\), as we are only storing the integer res for the result and a few helper variables. No additional data structures are used that scale with the input size.

Code

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        COLS = len(matrix[0])
        ROWS = len(matrix)
        n = min(COLS, ROWS)
        res = 0
        for size in range(1, n + 1):
            for row in range(ROWS):
                for col in range(COLS):
                    rs, re = row, row + size
                    cs, ce = col, col + size
                    if re > ROWS or ce > COLS:
                        break
                    res += self.is_valid_submatrix(rs, re, cs, ce, matrix)

        return res

    def is_valid_submatrix(self, rs, re, cs, ce, matrix):
        for row in range(rs, re):
            for col in range(cs, ce):
                if matrix[row][col] != 1:
                    return False
        return True

Editorial

Approach 1: Top-Down Dynamic Programming

class Solution:
    def solve(self, i, j, grid, dp):
        # If the cell lies outside the grid, return 0.
        if i >= len(grid) or j >= len(grid[0]):
            return 0
        if grid[i][j] == 0:
            return 0
        # If we have already visited this cell, return the memoized value.
        if dp[i][j] != -1:
            return dp[i][j]
        # Find the answer for the cell to the right of the current cell.
        right = self.solve(i, j + 1, grid, dp)
        # Find the answer for the cell to the diagonal of the current cell.
        diagonal = self.solve(i + 1, j + 1, grid, dp)
        # Find the answer for the cell below the current cell.
        below = self.solve(i + 1, j, grid, dp)
        dp[i][j] = 1 + min(right, min(diagonal, below))
        return dp[i][j]

    def countSquares(self, matrix: List[List[int]]) -> int:
        ans = 0
        dp = [[-1 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                ans += self.solve(i, j, matrix, dp)
        return ans

• time: O(mn)
• space: O(mn)