💡 Problem Formulation: The challenge is to write a program that can efficiently count the total number of square submatrices that have all ones in a binary matrix. Given a 2D binary matrix filled with 0’s and 1’s, the goal is to determine the count of square submatrices with all 1’s. For instance, the input [[1,0,1],[1,1,0],[1,1,0]] should return an output of 7.
Method 1: Dynamic Programming
This approach uses dynamic programming to build a solution incrementally. The idea is to traverse the matrix while keeping track of the size of the largest square submatrix ending at each position that only includes ones. This method is efficient and avoids redundant computations.
Here’s an example:
def countSquares(matrix):
rows, cols = len(matrix), len(matrix[0])
count = 0
for r in range(rows):
for c in range(cols):
if matrix[r][c] == 1:
if r == 0 or c == 0:
count += 1
else:
cell_val = min(matrix[r-1][c], matrix[r][c-1], matrix[r-1][c-1]) + matrix[r][c]
count += cell_val
matrix[r][c] = cell_val
return count
matrix = [[1,0,1],[1,1,0],[1,1,0]]
print(countSquares(matrix))Output: 7
This code snippet defines a function countSquares() that accepts a binary matrix and returns the count of square submatrices with all 1’s. The dynamic programming solution iteratively updates the matrix in place, and the count is incremented accordingly.
Method 2: Brute Force with Optimization
This brute force method checks every possible square submatrix but uses optimizations to skip unnecessary checks. Submatrices are considered only if their starting cell is ‘1’, and further checks are done to confirm all member cells are ‘1’. Despite its simplicity, this method is less efficient than dynamic programming for larger matrices.
Here’s an example:
def isSquareAllOnes(matrix, top, left, size):
for r in range(top, top + size):
for c in range(left, left + size):
if matrix[r][c] == 0:
return False
return True
def countSquares(matrix):
rows, cols = len(matrix), len(matrix[0])
count = 0
maxSize = min(rows, cols)
for r in range(rows):
for c in range(cols):
if matrix[r][c] == 1:
for size in range(1, maxSize+1):
if r+size <= rows and c+size <= cols and isSquareAllOnes(matrix, r, c, size):
count += 1
else:
break
return count
matrix = [[1,0,1],[1,1,0],[1,1,0]]
print(countSquares(matrix))Output: 7
The function isSquareAllOnes() checks whether a square submatrix all contains ones, and countSquares() applies this check iteratively while optimizing size checks.
Method 3: Depth-First Search (DFS)
The DFS approach recursively explores each potential submatrix starting from each ‘1’ in the matrix. The search expands while consecutive ones are found, counting each valid square submatrix. This method can be intuitive but may be more cumbersome for larger matrices due to recursive calls leading to potential stack overflows.
Here’s an example:
def dfs(matrix, row, col, rows, cols):
if row >= rows or col >= cols or matrix[row][col] == 0:
return 0
down = dfs(matrix, row+1, col, rows, cols)
right = dfs(matrix, row, col+1, rows, cols)
diag = dfs(matrix, row+1, col+1, rows, cols)
return 1 + min(down, right, diag)
def countSquares(matrix):
rows, cols = len(matrix), len(matrix[0])
count = 0
for r in range(rows):
for c in range(cols):
if matrix[r][c] == 1:
count += dfs(matrix, r, c, rows, cols)
return count
matrix = [[1,0,1],[1,1,0],[1,1,0]]
print(countSquares(matrix))Output: 7
This example uses the depth-first search algorithm in a function dfs() to explore and count square submatrices starting with ‘1’s, while countSquares() calls dfs() for each cell in the matrix.
Method 4: Breadth-First Search (BFS)
BFS uses a queue to iteratively explore levels of potential square submatrices, layer by layer. Starting at ‘1’s, it checks for larger squares by adding each new level found to a queue for further exploration. BFS can be easier to handle for large data sets as it does not rely on recursion, thus avoiding stack overflow issues. However, it requires additional memory for the queue.
Here’s an example:
from collections import deque
def bfs(matrix, row, col, rows, cols):
queue = deque([(row, col, 1)])
total = 0
while queue:
r, c, size = queue.popleft()
if (r+size > rows) or (c+size > cols):
continue
for delta_r in range(size):
if matrix[r+delta_r][c+size-1] == 0:
return total
for delta_c in range(size-1):
if matrix[r+size-1][c+delta_c] == 0:
return total
total += 1
queue.append((r, c, size+1))
return total
def countSquares(matrix):
rows, cols = len(matrix), len(matrix[0])
count = 0
for r in range(rows):
for c in range(cols):
if matrix[r][c] == 1:
count += bfs(matrix, r, c, rows, cols)
return count
matrix = [[1,0,1],[1,1,0],[1,1,0]]
print(countSquares(matrix))Output: 7
The bfs() function performs a breadth-first search and countSquares() calls this function for each cell of the matrix. It utilizes a queue to manage subsets of submatrices to verify.
Bonus One-Liner Method 5: Functional Programming
This technique uses functional programming with Python’s built-in functions and list comprehension to create a one-liner solution. It is elegant but may be difficult to interpret. This is not always the most efficient, but useful for concise coding or small data sets.
Here’s an example:
countSquares = lambda m: sum(
min(m[i-1][j], m[i][j-1], m[i-1][j-1]) + 1 if i * j * m[i][j] else m[i][j]
for i in range(len(m))
for j in range(len(m[0]))
if (m[i][j] := m[i][j])
)
matrix = [[1,0,1],[1,1,0],[1,1,0]]
print(countSquares(matrix))Output: 7
This one-liner redefines the matrix in-place and calculates the count in a single expression, using lambda and list comprehension.
Summary/Discussion
- Method 1: Dynamic Programming. This method offers optimal performance with reduced time complexity. However, it requires a good understanding of dynamic programming concepts for implementation.
- Method 2: Brute Force with Optimization. This solution is straightforward but not as efficient, especially as the size of the matrix increases, due to the nested iterations.
- Method 3: Depth-First Search. DFS provides an algorithmic and recursive way to solve the problem, but may lead to performance issues with very large matrices.
- Method 4: Breadth-First Search. BFS avoids the recursive pitfalls of DFS, but uses more memory due to the need for maintaining a queue.
- Bonus One-Liner Method 5: Functional Programming. This method is elegant and quick to write but less transparent and can be less efficient due to its condensed nature.