Question

from typing import List

def longest_chain(submatrix: List[int]) -> int:
"""
Given a list of integers, return the length of the longest chain of 1's
that start from the beginning.

You MUST use a while loop for this! We will check.

>>> longest_chain([1, 1, 0])
2
>>> longest_chain([0, 1, 1])
0
>>> longest_chain([1, 0, 1])
1
"""
i = 0
a = []
while i < len(submatrix) and submatrix[i] != 0:
a.append(submatrix[i])
i += 1
return sum(a)

def largest_rectangle_at_position(matrix: List[List[int]], x: int, y: int
) -> int:
"""
Returns the area of the largest rectangle whose top left corner is at
position , in .

You MUST make use of here as you loop through each row
of the matrix. Do not modify the input matrix.

>>> case1 = [[1, 0, 1, 0, 0],
... [1, 0, 1, 1, 1],
... [1, 1, 1, 1, 1],
... [1, 0, 0, 1, 0]]
>>> largest_rectangle_at_position(case1, 0, 0)
4
>>> largest_rectangle_at_position(case1, 2, 0)
5
>>> largest_rectangle_at_position(case1, 1, 2)
6
"""

pass

replace the word pass with a function body by implementing the 1st function. make sure nested loops can be a max of 3. try to keep it as short as possible and fulfill the docstring requirements

Answer 1

from typing import List


def longest_chain(submatrix : List[int]) ->int:
    i = 0
    a = []
    while i < len(submatrix) and submatrix[i] != 0:
        a.append(submatrix[i])
        i += 1
    return sum(a)

def largest_rectangle_at_position(matrix: List[List[int]], x: int, y: int) -> int:
    temp = []
    # calculating the longest chain
    for i in range(x, len(matrix)):
        temp.append( longest_chain(matrix[i][y:]))
    max = 0
    # longest chain will not be longer than first element of temp Array
    # it can be less but not more than that
    firstMax = temp[0]
    for elem in set(temp):
        # if elem is more then we should not move further
        if elem > firstMax :
            continue
        # calculating count
        cnt = 0
        for i in range(len(temp)):
            if elem <= temp[i]:
                cnt += 1
        # calculating max
        if max < cnt * elem:
            max = cnt * elem

    return max


case1 = [
    [1, 0, 1, 0, 0],
    [1, 0, 1, 1, 1],
    [1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0]
]

print(largest_rectangle_at_position(case1, 0, 0))
print(largest_rectangle_at_position(case1, 2, 0))
print(largest_rectangle_at_position(case1, 1, 2))
print(largest_rectangle_at_position(case1, 1, 4))

Code

Output