Largest Rectangle in a Matrix. How to combine programming techniques | by Shuo Wang | Jan, 2021

[ad_1]


Solution #1

How to do this simply

The first time I tried out this problem, I thought to myself:

Well, it looks like I probably need to iterate through every point in the matrix, and at each point, I need to find the largest rectangle containing that point. I’ll compare that rectangle to the size of the rectangles I have already found. If the new one is bigger, I’ll keep it, otherwise I move on to the next point.

This sounds great, but there is a problem with it. How do I find the largest rectangle containing a particular point. Nothing comes to mind that would help me solve this problem.

What if I just want to find the largest rectangle that has the current point as its top left corner? I think this is a more manageable problem.

In order for me to figure that out, I’ll loop through each point to the right of my current point, at each point I find the maximum height of blue dots, if it’s smaller than the height at the current point, I’ll update the current point height to the new height and find the size of the new rectangle, if it’s a bigger rectangle I’ll update the max size.

Let’s apply this procedure to our example.

Suppose I have looped to point (1, 0):

(Image by Author)

I find the height of my current point, which is 2, the largest rectangle with (1, 0) as top right corner given this information is also 2.

(1, 0): height = 2, max_rectangle = 2.

I iterate through every point to the right:

Point (2, 0) has a height of 3, but it’s larger than the starting point, so the height is still 2. But now we know that we can have a rectangle of size 2 * 2 = 4:

(2, 0): height = 2, max_rectangle = 4

Point (3, 0) has a height of 1, it’s smaller than current height, so we update current height to 1, the rectangle that can be created is: 1 * 3 = 3, but the current max is 4, so we ignore it:

(3, 0): height = 1, max_rectangle = 4

Going through the same process for the rest of points:

(4, 0): height = 1, max_rectangle = 4

(5, 0): height = 1, max_rectangle = 5

we find the largest rectangle with top right corner of (1, 0) to be of size 5.

Let’s put this into code:

def find_max001(matrix):

width = len(matrix[0])
height = len(matrix)

# max width and max height at the a point
# uses memorization and dynamic programming
max_matrix = [[None for v in row] for row in matrix]
def get_max(i, j):
if i >= width:
return 0, 0
elif j >= height:
return 0, 0
elif max_matrix[j][i] is not None:
return max_matrix[j][i]
elif matrix[j][i] == 0:
max_matrix[j][i] = (0, 0)
return max_matrix[j][i]

max_down = get_max(i, j + 1)
max_right = get_max(i + 1, j)

max_matrix[j][i] = (max_right[0] + 1,
max_down[1] + 1)
return max_matrix[j][i]

max_rect = 0
for i in range(width):
for j in range(height):
rect = get_max(i, j)
cur_max = rect[1]
for k in range(1, rect[0]):
cur_max = min(cur_max, get_max(i+k, j)[1])

max_rect = max(max_rect, cur_max * rect[0])

return max_rect

def problem003(solver):

m001 = [
[1, 1, 1, 1, 1, 1],
[0, 1, 1, 0, 1, 1],
[0, 0, 1, 0, 1, 1],
[0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 0]
]

res1 = solver(m001)
print(f'res1: {res1}')

def test003():
solver = find_max001
problem003(solver)
test003()
# res1: 8

Read More …

[ad_2]


Write a comment