NUHMAN.com

Introduction

LeetCode 85: Maximal Rectangle is an extension of the Largest Rectangle in Histogram problem. Here, instead of a single histogram, you're given a 2D binary matrix, and the task is to find the area of the largest rectangle containing only 1's.

This problem can be solved efficiently using a dynamic programming approach combined with a monotonic stack—just like the Largest Rectangle in Histogram problem, but adapted for a matrix.

Problem Statement

Given a 2D binary matrix filled with 0's and 1's, find the area of the largest rectangle containing only 1's and return its area.

Example:

go

Input: matrix = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

Explanation: The maximal rectangle is shown in the second row, which is 3×2 = 6.

Approach: Dynamic Programming + Monotonic Stack

Idea:

• The problem can be reduced to multiple Largest Rectangle in Histogram problems by treating each row as the base of a histogram.
• We can build a histogram for each row, where each column represents the height of 1's up to the current row. As we move row by row, we update the histogram.
• Once we have the histogram for each row, we use the monotonic stack method (from LeetCode 84) to calculate the largest rectangle for that row's histogram.

Algorithm Steps:

1. For each row in the matrix, update the histogram's heights:

• If the matrix cell is 1, increment the corresponding height; otherwise, reset it to 0.

1. For each updated histogram, apply the Largest Rectangle in Histogram algorithm to calculate the maximum rectangle area.
2. Track the largest rectangle found.

Go Implementation

go

func maximalRectangle(matrix [][]byte) int {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return 0
    }

    // Convert matrix rows to integers for easier calculations
    heights := make([]int, len(matrix[0]))
    maxArea := 0

    for _, row := range matrix {
        for i := 0; i < len(row); i++ {
            // Update heights: if the cell is 1, increment height; otherwise, reset to 0
            if row[i] == '1' {
                heights[i]++
            } else {
                heights[i] = 0
            }
        }

        // Calculate the largest rectangle for the current histogram
        maxArea = max(maxArea, largestRectangleArea(heights))
    }

    return maxArea
}

func largestRectangleArea(heights []int) int {
    stack := []int{}
    maxArea := 0
    heights = append(heights, 0) // Sentinel to flush the stack

    for i := 0; i < len(heights); i++ {
        for len(stack) > 0 && heights[i] < heights[stack[len(stack)-1]] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]

            height := heights[top]
            width := i
            if len(stack) > 0 {
                width = i - stack[len(stack)-1] - 1
            }

            area := height * width
            if area > maxArea {
                maxArea = area
            }
        }
        stack = append(stack, i)
    }

    return maxArea
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation

• heights array: This stores the height of the histogram for each column at the current row.
• If the value in the matrix is 1, the height is incremented.
• If the value is 0, the height is reset to 0.
• largestRectangleArea function: This function calculates the maximum area of a rectangle in a histogram using the monotonic stack approach.
• Loop through each row: We update the heights array and then calculate the largest rectangle for the updated histogram.
• Helper function max: It returns the larger of two values, used for tracking the maximum area.

Time and Space Complexity

MetricComplexityTime ComplexityO(m * n)Space ComplexityO(n)

Where m is the number of rows and n is the number of columns in the matrix.

Edge Cases

• Empty matrix: The function returns 0.
• Matrix with all 0's: The function returns 0.
• Matrix with all 1's: The function computes the maximum area based on the entire matrix.
• Non-rectangular matrices: The algorithm works for any matrix size (not just square).

Conclusion

LeetCode 85 challenges you to extend the solution for the Largest Rectangle in Histogram problem to a 2D matrix. By using a dynamic programming approach with a monotonic stack, you can efficiently compute the largest rectangle area for each row, then combine the results to get the final answer.

This problem is an excellent demonstration of dynamic programming combined with stack-based algorithms, and it's a useful technique for solving problems involving 2D grids.