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 1
s 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
-
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. -
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. -
Check submatrix validity: For each potential square, check all cells to ensure they contain only
1
s by defining a helper method,is_valid_submatrix
. This function returnsTrue
if all cells are1
s andFalse
otherwise. -
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)