Rectangle Measurement

2022-02-28.py

question = """

Given a 2D array of 0s and 1s, return the size of the largest rectangle of 1s in the array.

Example:

let islands = [
0,0,0,1,0
1,1,0,0,1
1,1,0,0,0
0,0,1,0,0
]

$ largestRect(islands)
$ '2x2'

"""
from itertools import product

# need to not require inside values to be 1
# only measure outer edge of rectangle

def measureRect(matrix, start_x, start_y, end_x, end_y):
    sum = 0
    space = 0
    for x in range(end_x - start_x + 1):
        for y in range(end_y - start_y + 1):
            if start_x + x == start_x or start_x + x == end_x or start_y + y == start_y or start_y + y == end_y:
                sum += int(matrix[start_x + x][start_y + y])
                space += 1
    if sum == space:
        return sum, space
    else:
        return 0, -1

def largestRect(matrix):
    m = len(matrix)
    n = len(matrix[0])
    l = 0
    biggest_xy = (0,0)
    for x, y in product(range(m), range(n)):
        if matrix[x][y] == 1:
            # top-left corner
            sum = 0
            space = 0
            for x1, y1 in product(range(m - x), range(n - y)):
                if matrix[x + x1][y + y1] == 1:
                    # possible bottom-right corner
                    if x1 == 0 or y1 == 0:
                        continue                    
                    sum, space = measureRect(matrix, x, y, x + x1, y + y1)
                    if space == sum:
                        if l < sum:
                            l = sum
                            biggest_xy = (x1+1, y1+1)

    return 'x'.join(map(lambda x: str(x), biggest_xy))

islands = [
    [0,0,0,1,0],
    [1,1,0,0,1],
    [1,1,0,0,0],
    [0,0,1,0,0]
]

print(largestRect(islands))

# solid rectangle

islands = [
    [0,0,0,1,0],
    [1,1,1,0,1],
    [1,1,1,0,0],
    [1,1,1,0,0]
]

print(largestRect(islands))

# hollow rectangle

islands = [
    [0,0,0,1,0],
    [1,1,1,0,1],
    [1,0,1,0,0],
    [1,1,1,0,0]
]

print(largestRect(islands))