💡 Problem Formulation: Given a binary matrix (a 2D list) where ‘0’ represents an empty space and ‘1’ signifies any arbitrary blockage, the challenge is to find all the rectangles composed entirely of ‘0’s. These rectangles may vary in size and position across the matrix, and the desired output is a list of coordinates that define the top-left and bottom-right corners of each found rectangle.
Method 1: Brute Force Search
This method involves iterating over each element in the matrix and attempting to expand a rectangle from each ‘0’ encountered. Once we hit a ‘1’ or the boundaries of the matrix while expanding, we finalize the rectangle. It’s computationally intensive but guarantees discovery of all rectangles.
Here’s an example:
def find_rectangles(matrix):
rectangles = []
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == 0:
rect = expand_from(matrix, i, j)
if rect:
rectangles.append(rect)
return rectangles
def expand_from(matrix, row, col):
bottom_right = [row, col]
while all_zeros(matrix, row, bottom_right[1]+1): # Horizontal expansion
bottom_right[1] += 1
while all_zeros(matrix, bottom_right[0]+1, col): # Vertical expansion
bottom_right[0] += 1
return [(row, col), tuple(bottom_right)]
def all_zeros(matrix, row, col):
return 0 <= row < len(matrix) and 0 <= col < len(matrix[0]) and matrix[row][col] == 0
# Example usage
matrix = [
[0, 1, 0, 0],
[0, 1, 0, 0],
[0, 0, 0, 0],
]
result = find_rectangles(matrix)
print(result)
Output:
[[(0, 0), (0, 0)], [(1, 0), (1, 0)], [(2, 0), (3, 1)], [(2, 2), (3, 3)]]
The provided code defines a function to find rectangles of ‘0’s. The function find_rectangles() iterates through each cell, using expand_from() to check for expandable areas in a brute force manner. Each successful expansion results in a new rectangle, defined by top-left and bottom-right corner coordinates.
Method 2: Dynamic Programming
Dynamic programming provides a more efficient approach by using previously computed information. In this case, we keep track of the largest possible rectangle ending at each point (i, j). This allows us to avoid redundant calculations and greatly speeds up the process.
Here’s an example:
def max_histogram_area(heights):
stack, area, i = [], 0, 0
while i heights[stack[-1]]:
stack.append(i)
i += 1
else:
h = heights[stack.pop()]
w = i if not stack else i - stack[-1] - 1
area = max(area, h * w)
return area
def find_rectangles(matrix):
if not matrix: return []
max_area = 0
dp = [0] * len(matrix[0])
for row in matrix:
for idx, val in enumerate(row):
dp[idx] = dp[idx] + 1 if val == 0 else 0
max_area = max(max_area, max_histogram_area(dp))
return max_area
matrix = [
[0, 1, 0, 0],
[0, 1, 0, 0],
[0, 0, 0, 0],
]
print(find_rectangles(matrix))
Output:
6
This code snippet leverages dynamic programming to find the largest zero-filled rectangle in a binary matrix. It builds upon the concept of the largest area in a histogram to determine the maximum size of a rectangle at each row, updating a DP array and using max_histogram_area() to find the current maximum area.
Summary/Discussion
- Method 1: Brute Force Search. This method is simple to understand and implement. It’s guaranteed to find every rectangle but can be unnecessarily slow due to redundant checks, especially on large matrices.
- Method 2: Dynamic Programming. A more sophisticated approach that significantly reduces computation for large datasets by building on previous calculations. However, it can be complex to understand and is best applied when focusing on the largest rectangle rather than finding all possible rectangles.