question given a binary matrix mat of size n m find out the maximum size square submatrix with all 1s example 1 input n 2 m 2 mat 1 1 1 1 output 2 explanation the maximum size of the square submatrix is 2 the matrix itself is the maximum sized submatrix in this case example 2 input n 2 m 2 mat 0 0 0 0 output 0 explanation there is no 1 in the matrix approach we initialize another matrix dp with the same dimensions as the original one initialized with all 0s dparrayi j represents the side length of the maximum square whose bottom right corner is the cell with index i j in the original matrix starting from index 0 0 for every 1 found in the original matrix we update the value of the current element as dparrayi jdparraydpi1 j dparrayi1 j1 dparrayi j1 1 function updates the largestsquarearea0 if recursive call found square with maximum area we aren t using dparray here so the time complexity would be exponential largestsquareareainmatrixtopdownapproch2 2 1 1 1 1 2 largestsquareareainmatrixtopdownapproch2 2 0 0 0 0 0 base case function updates the largestsquarearea0 if recursive call found square with maximum area we are using dparray here so the time complexity would be on2 largestsquareareainmatrixtopdownapprochwithdp2 2 1 1 1 1 2 largestsquareareainmatrixtopdownapprochwithdp2 2 0 0 0 0 0 function updates the largestsquarearea using bottom up approach largestsquareareainmatrixbottomup2 2 1 1 1 1 2 largestsquareareainmatrixbottomup2 2 0 0 0 0 0 function updates the largestsquarearea using bottom up approach with space optimization largestsquareareainmatrixbottomupspaceoptimization2 2 1 1 1 1 2 largestsquareareainmatrixbottomupspaceoptimization2 2 0 0 0 0 0 function updates the largest_square_area 0 if recursive call found square with maximum area we aren t using dp_array here so the time complexity would be exponential largest_square_area_in_matrix_top_down_approch 2 2 1 1 1 1 2 largest_square_area_in_matrix_top_down_approch 2 2 0 0 0 0 0 base case function updates the largest_square_area 0 if recursive call found square with maximum area we are using dp_array here so the time complexity would be o n 2 largest_square_area_in_matrix_top_down_approch_with_dp 2 2 1 1 1 1 2 largest_square_area_in_matrix_top_down_approch_with_dp 2 2 0 0 0 0 0 function updates the largest_square_area using bottom up approach largest_square_area_in_matrix_bottom_up 2 2 1 1 1 1 2 largest_square_area_in_matrix_bottom_up 2 2 0 0 0 0 0 function updates the largest_square_area using bottom up approach with space optimization largest_square_area_in_matrix_bottom_up_space_optimization 2 2 1 1 1 1 2 largest_square_area_in_matrix_bottom_up_space_optimization 2 2 0 0 0 0 0
def largest_square_area_in_matrix_top_down_approch(
    rows: int, cols: int, mat: list[list[int]]
) -> int:
    

    def update_area_of_max_square(row: int, col: int) -> int:
        
        if row >= rows or col >= cols:
            return 0

        right = update_area_of_max_square(row, col + 1)
        diagonal = update_area_of_max_square(row + 1, col + 1)
        down = update_area_of_max_square(row + 1, col)

        if mat[row][col]:
            sub_problem_sol = 1 + min([right, diagonal, down])
            largest_square_area[0] = max(largest_square_area[0], sub_problem_sol)
            return sub_problem_sol
        else:
            return 0

    largest_square_area = [0]
    update_area_of_max_square(0, 0)
    return largest_square_area[0]


def largest_square_area_in_matrix_top_down_approch_with_dp(
    rows: int, cols: int, mat: list[list[int]]
) -> int:
    

    def update_area_of_max_square_using_dp_array(
        row: int, col: int, dp_array: list[list[int]]
    ) -> int:
        if row >= rows or col >= cols:
            return 0
        if dp_array[row][col] != -1:
            return dp_array[row][col]

        right = update_area_of_max_square_using_dp_array(row, col + 1, dp_array)
        diagonal = update_area_of_max_square_using_dp_array(row + 1, col + 1, dp_array)
        down = update_area_of_max_square_using_dp_array(row + 1, col, dp_array)

        if mat[row][col]:
            sub_problem_sol = 1 + min([right, diagonal, down])
            largest_square_area[0] = max(largest_square_area[0], sub_problem_sol)
            dp_array[row][col] = sub_problem_sol
            return sub_problem_sol
        else:
            return 0

    largest_square_area = [0]
    dp_array = [[-1] * cols for _ in range(rows)]
    update_area_of_max_square_using_dp_array(0, 0, dp_array)

    return largest_square_area[0]


def largest_square_area_in_matrix_bottom_up(
    rows: int, cols: int, mat: list[list[int]]
) -> int:
    
    dp_array = [[0] * (cols + 1) for _ in range(rows + 1)]
    largest_square_area = 0
    for row in range(rows - 1, -1, -1):
        for col in range(cols - 1, -1, -1):
            right = dp_array[row][col + 1]
            diagonal = dp_array[row + 1][col + 1]
            bottom = dp_array[row + 1][col]

            if mat[row][col] == 1:
                dp_array[row][col] = 1 + min(right, diagonal, bottom)
                largest_square_area = max(dp_array[row][col], largest_square_area)
            else:
                dp_array[row][col] = 0

    return largest_square_area


def largest_square_area_in_matrix_bottom_up_space_optimization(
    rows: int, cols: int, mat: list[list[int]]
) -> int:
    
    current_row = [0] * (cols + 1)
    next_row = [0] * (cols + 1)
    largest_square_area = 0
    for row in range(rows - 1, -1, -1):
        for col in range(cols - 1, -1, -1):
            right = current_row[col + 1]
            diagonal = next_row[col + 1]
            bottom = next_row[col]

            if mat[row][col] == 1:
                current_row[col] = 1 + min(right, diagonal, bottom)
                largest_square_area = max(current_row[col], largest_square_area)
            else:
                current_row[col] = 0
        next_row = current_row

    return largest_square_area


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    print(largest_square_area_in_matrix_bottom_up(2, 2, [[1, 1], [1, 1]]))