LeetCode 85: Maximal Rectangle Solution in Python Explained

Copy codeInput: matrix = [["1","0","1","0","0"],
                 ["1","0","1","1","1"],
                 ["1","1","1","1","1"],
                 ["1","0","0","1","0"]]
Output: 6
Explanation: Largest rectangle is 2 rows by 3 columns of 1s (area = 2 * 3 = 6).

Copy codeInput: matrix = [["0","1"],
                 ["1","0"]]
Output: 1
Explanation: Largest is a single 1 (area = 1).

Copy codeInput: matrix = [["1"]]
Output: 1
Explanation: Single 1 (area = 1).

Copy codedef maximalRectangle(matrix: list[list[str]]) -> int:
    # Line 1: Check if matrix is empty
    if not matrix or not matrix[0]:
        # If matrix is empty (no rows) or first row is empty (no columns), no rectangle possible
        return 0

    # Line 2: Get dimensions
    rows, cols = len(matrix), len(matrix[0])
    # rows = number of rows (e.g., 4), cols = number of columns (e.g., 5)

    # Line 3: Initialize heights array for histogram
    heights = [0] * cols
    # Creates an array of zeros with length equal to columns (e.g., [0,0,0,0,0])
    # Will track consecutive 1s for each column as we process rows

    # Line 4: Initialize max_area to track largest rectangle
    max_area = 0
    # Starts at 0, will update with the largest area found across all histograms

    # Line 5: Iterate through each row of the matrix
    for i in range(rows):
        # i goes from 0 to rows-1, processing each row (e.g., 0 to 3)

        #+ Line 6: Update heights array based on current row
        for j in range(cols):
            # j goes from 0 to cols-1, updating each column’s height
            if matrix[i][j] == "1":
                # If current cell is "1", increment height for this column
                # e.g., heights[j] = 1 becomes 2 if previous row had a 1 above
                heights[j] += 1
            else:
                # If cell is "0", reset height to 0 (no consecutive 1s)
                # e.g., heights[j] = 2 becomes 0
                heights[j] = 0

        # Line 7: Add sentinels to heights for stack processing
        heights_with_sentinels = [0] + heights + [0]
        # Prepends and appends 0 (e.g., [0,1,0,1,0,0] for [1,0,1,0,0])
        # Ensures all bars are processed by triggering pops at edges

        # Line 8: Initialize stack with -1 as left boundary
        stack = [-1]
        # Stack stores indices in increasing height order, -1 is a sentinel

        # Line 9: Process the histogram using stack
        for k in range(len(heights_with_sentinels)):
            # k iterates over all indices in heights_with_sentinels (e.g., 0 to 6)

            # Line 10: While stack has bars and current height is less than top
            while stack[-1] != -1 and heights_with_sentinels[stack[-1]] > heights_with_sentinels[k]:
                # Checks if stack isn’t just [-1] and top bar is taller than current
                # e.g., 2 > 0 triggers a pop

                # Line 11: Pop the top index and get its height
                h = heights_with_sentinels[stack.pop()]
                # Removes top index (e.g., 4 for height 2) and gets height (h = 2)
                # This bar can’t extend further right

                # Line 12: Calculate width
                w = k - stack[-1] - 1
                # Width = current index - new top index - 1
                # e.g., k = 5, stack[-1] = 2, w = 5 - 2 - 1 = 2

                # Line 13: Update max_area if this area is larger
                max_area = max(max_area, h * w)
                # Area = height * width (e.g., 2 * 3 = 6), updates max_area if bigger

            # Line 14: Append current index to stack
            stack.append(k)
            # Adds current index (e.g., 5) to stack for future pops

    # Line 15: Return the largest area found
    return max_area
    # Returns the maximum area across all row histograms (e.g., 6)

Copy codedef maximalRectangleBrute(matrix: list[list[str]]) -> int:
    if not matrix or not matrix[0]:
        return 0
    rows, cols = len(matrix), len(matrix[0])
    max_area = 0
    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == "1":
                width = 0
                while j + width < cols and matrix[i][j + width] == "1":
                    height = 0
                    while i + height < rows and all(matrix[i + h][j:j + width + 1] == ["1"] * (width + 1) for h in range(height + 1)):
                        height += 1
                    max_area = max(max_area, (width + 1) * height)
                    width += 1
    return max_area