💡 Problem Formulation: Given a 2D binary matrix, where 0 represents an empty field and 1 represents a filled field, we aim to count all the rectangles or submatrices composed exclusively of 1s. For instance, given the matrix [[1,0,1],[1,1,0],[1,1,0]], we intend to return a count of submatrices with all ones, which in this case should be 13.
Method 1: Dynamic Programming Approach
This method utilizes dynamic programming to keep track of the number of continuous ones in each row while traversing the matrix. Based on these counts, it calculates the number of submatrices ending at each position. It is efficient as it avoids recalculating for each position and only processes non-zero values.
Here’s an example:
def countSubmatricesWithAllOnes(matrix):
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
result = 0
for i in range(m):
for j in range(n):
if matrix[i][j]:
matrix[i][j] += matrix[i][j-1] if j else 0
min_width = matrix[i][j]
for k in range(i, -1, -1):
min_width = min(min_width, matrix[k][j])
result += min_width
return result
# Example matrix
matrix = [
[1,0,1],
[1,1,0],
[1,1,0]
]
print(countSubmatricesWithAllOnes(matrix))
Output: 13
The provided Python function countSubmatricesWithAllOnes takes a 2D list (matrix) and returns the count of all submatrices with all ones. It modifies the original matrix to store the count of continuous ones ending in that cell horizontally. It then iterates over all possible bottom-right ends of submatrices, computes the maximum width for that submatrix, and adds up these to return the final count.
Method 2: Histogram-Based Approach
This method transforms each row of the matrix into a histogram, where the height of the bar at each column is the count of consecutive ones up to that point in the same column. It then uses a stack to efficiently calculate the number of rectangles that can be formed from each histogram.
Here’s an example:
def countSubmatricesWithAllOnes(matrix):
def countRectangles(heights):
stack = []
answer = 0
for i, h in enumerate(heights):
start = i
while stack and stack[-1][1] > h:
index, height = stack.pop()
start = index
answer += height * (i - index)
stack.append((start, h))
for i, h in stack:
answer += h * (len(heights) - i)
return answer
for i in range(1, len(matrix)):
for j in range(len(matrix[i])):
matrix[i][j] *= matrix[i-1][j] + 1 if matrix[i][j] else 0
return sum(countRectangles(row) for row in matrix)
# Example matrix
matrix = [
[1,0,1],
[1,1,0],
[1,1,0]
]
print(countSubmatricesWithAllOnes(matrix))
Output: 13
The function countSubmatricesWithAllOnes starts by converting the binary matrix into a histogram representation for each row. It then applies the function countRectangles on each row, which leverages a stack to compute the number of rectangles for the histogram, efficiently handling the column bars and their extension for possible rectangles. The algorithm sums up results from all rows to find the total count.
Method 3: Brute Force Enumeration
Brute force enumeration iterates through each cell of the matrix and, for each cell, explores all possible submatrices for which the current cell is the upper-left corner. It directly counts the submatrices with all ones, though is not efficient for larger matrices due to its high computational complexity.
Here’s an example:
def countSubmatricesWithAllOnes(matrix):
def isAllOnes(i1, j1, i2, j2):
for i in range(i1, i2+1):
for j in range(j1, j2+1):
if matrix[i][j] == 0:
return False
return True
count = 0
for i in range(len(matrix)):
for j in range(len(matrix[0])):
for k in range(i, len(matrix)):
for l in range(j, len(matrix[0])):
if isAllOnes(i, j, k, l):
count += 1
return count
# Example matrix
matrix = [
[1,0,1],
[1,1,0],
[1,1,0]
]
print(countSubmatricesWithAllOnes(matrix))
Output: 13
Here, the nested loops in countSubmatricesWithAllOnes function iterate through all the cells, using them as a starting point for submatrices and further nested loops examine all possible submatrices to check if they are composed entirely of ones using the helper function isAllOnes. This method returns the correct count but is inefficient for complex scenarios.
Method 4: Optimized Enumeration with Prefix Sum
Optimized enumeration refines the brute force approach by computing a prefix sum matrix first, which helps in performing quick checks of whether a submatrix contains all ones. It still enumerates all possible submatrices but does so more efficiently by avoiding repeated calculations.
Here’s an example:
def countSubmatricesWithAllOnes(matrix):
m, n = len(matrix), len(matrix[0])
count = 0
pref = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
pref[i][j] = matrix[i-1][j-1] + \
pref[i][j-1] + pref[i-1][j] - \
pref[i-1][j-1]
for i1 in range(1, m+1):
for j1 in range(1, n+1):
for i2 in range(i1, m+1):
for j2 in range(j1, n+1):
if (pref[i2][j2] - pref[i1-1][j2] -
pref[i2][j1-1] + pref[i1-1][j1-1] ==
(i2-i1+1) * (j2-j1+1)):
count += 1
return count
# Example matrix
matrix = [
[1,0,1],
[1,1,0],
[1,1,0]
]
print(countSubmatricesWithAllOnes(matrix))
Output: 13
The countSubmatricesWithAllOnes function computes a prefix sum matrix that aids in querying the sum of any submatrix in constant time. Let \((i1, j1)\) be the upper-left and \((i2, j2)\) be the bottom-right corners of a submatrix, we can quickly determine if this submatrix is full of ones by checking if the sum equals the area size. This optimization significantly reduces computation time as compared to the brute force method.
Bonus One-Liner Method 5: List Comprehension with Min Function
This one-liner is a compact version of the dynamic programming approach, using Python list comprehensions and the min function to count submatrices. While it is elegant and takes advantage of Python’s expressiveness, it might be less readable and harder to debug than the more verbose methods.
Here’s an example:
countSubmatricesWithAllOnes = lambda matrix: sum(min(matrix[i][j] for i in range(k, -1, -1)) for k in range(len(matrix)) for j in range(len(matrix[0])) if matrix[k][j] for matrix[k][j] in [sum(matrix[k][:j+1])])
# Example matrix
matrix = [
[1,0,1],
[1,1,0],
[1,1,0]
]
print(countSubmatricesWithAllOnes(matrix))
Output: 13
This one-liner uses a lambda function to compress the logic of dynamic programming into a single expression. It iterates over all positions that have a one, sums the horizontal line of ones up to that point, keeps updating the current position value, and counts the possible submatrices. This demonstrates Python’s capability to write concise and somewhat complex algorithms in a very compact form.
Summary/Discussion
- Method 1: Dynamic Programming Approach. This method is highly efficient and scales well with matrix size. However, it does modify the original matrix, which may not always be desirable.
- Method 2: Histogram-Based Approach. Like the dynamic approach, this technique is efficient and does not modify the original matrix, but requires a deeper understanding of histograms and stacks, which might be challenging for beginners.
- Method 3: Brute Force Enumeration. This is the most straightforward method, easy to understand and implement, but it’s not suitable for large matrices due to its poor time complexity.
- Method 4: Optimized Enumeration with Prefix Sum. This method balances between brute force and dynamic programming approaches, providing a more efficient algorithm than brute force without being as complex as dynamic programming. However, it’s still less efficient than the dynamic programming approach.
- Bonus One-Liner Method 5: List Comprehension with Min Function. It’s the most concise method and a testament to Python’s expressiveness. Yet, it compromises readability and debuggability for brevity.