Maximum rectangle containing 1 in binary matrix

'''
Logic:
If we consider each row as a base and then find the maximum reactangle in histogram then you will get the maximum
rectange from the binary matrix.
'''
from typing import List

def largest_rectangle(arr):
    st = []
    st.append((0, -1))  # (index, prev_smaller_index)
    ans = float('-inf')
    n = len(arr)

    for i in range(1, n):
        while st and arr[st[-1][0]] >= arr[i]:
            idx, prev = st.pop()
            ans = max(ans, (i - prev - 1) * arr[idx])

        if not st:
            st.append((i, -1))
        else:
            st.append((i, st[-1][0]))

    while st:
        idx, prev = st.pop()
        ans = max(ans, (n - prev - 1) * arr[idx])

    return ans


class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0

        n, m = len(matrix), len(matrix[0])

        # convert to int
        matrix = [[int(x) for x in row] for row in matrix]

        ans = float('-inf')

        for i in range(n):
            if i != 0:
                for j in range(m):
                    if matrix[i][j] != 0:
                        matrix[i][j] += matrix[i - 1][j]
                    else:
                        matrix[i][j] = 0

            ans = max(ans, largest_rectangle(matrix[i]))

        return ans if ans != float('-inf') else 0