Maximal Rectangle LeetCode solution in Python

1
# Runtime: 1058 ms (Top 6.78%) | Memory: 15.2 MB (Top 89.63%)
2
class Solution:
3
    def maxArea(self, arr: List[List[int]]) -> int:
4
        maxA = 0  # local max variable to return max area of a 1D array
5
        stack = [
6
            -1
7
        ]  # initializing with minimum value so we can avoid using loop for remaining element in the stack after whole traversing
8
        arr.append(
9
            -1
10
        )  # value for stack index -1 and one extra iteration to empty the stack
11
        for i in range(len(arr)):  # traversing for stack from left to right
12
            arr[i] = int(arr[i])  # we are getting str value from matrix
13
            while stack and arr[stack[-1]] >= int(
14
                arr[i]
15
            ):  # stack is non empty and stack top is greater or equal to current element
16
                index = stack.pop()  # pop greater element from stack and finds its area
17
                width = (
18
                    i - stack[-1] - 1 if stack else i
19
                )  # for empty stack width is len of 1D arr, and after poping if we have element in stack then it becomes left boundary and current index as right boundary
20
                maxA = max(maxA, width * arr[index])  # geting max area (L * B)
21
            stack.append(int(i))  # inserting each element in stack
22
        return maxA  # return the max area
23

24
    """Below is the code for adding each row one by one and passing it to above function to get the max area for each row"""
25
    # r1 - 1 0 1 0 0
26
    # r2 - 1 0 1 1 1
27
    # r = 2 0 2 1 1 This is for else condition
28

29
    # r1 - 1 1 1 0 1
30
    # r2 - 1 0 1 1 0
31
    # r = 2 0 2 1 0 This is for if condition
32

33
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
34
        result = [0] * len(matrix[0])
35
        maxReact = 0
36
        maxReact = self.maxArea(result)
37
        for i in range(len(matrix)):
38
            for j in range(len(matrix[i])):
39
                matrix[i][j] = int(matrix[i][j])
40
                if matrix[i][j] == 0:
41
                    result[j] = 0
42
                else:
43
                    result[j] = result[j] + matrix[i][j]
44
            maxReact = max(
45
                maxReact, self.maxArea(result)
46
            )  # after getting max area for 1D arr we are getting max value from those 1D arr for the 2D arr
47
        return maxReact