85. Maximal Rectangle

[mah-shamim]

Topics: Array, Dynamic Programming, Stack, Matrix, Monotonic Stack

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example 1:

• 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 above picture.

Example 2:

• Input: matrix = [["0"]]
• Output: 0

Example 3:

• Input: matrix = [["1"]]
• Output: 1

Constraints:

• rows == matrix.length
• cols == matrix[i].length
• 1 <= row, cols <= 200
• matrix[i][j] is '0' or '1'.

[mah-shamim]

We can follow a dynamic programming approach. This problem can be effectively tackled by treating each row of the matrix as the base of a histogram, where the height of each column in the histogram represents the number of consecutive '1's up to that row.

1. Convert each row of the matrix into a histogram:
   • Treat each row as the base of a histogram where the height of each bar is the number of consecutive 1s up to that row.
2. Calculate the maximum area of the rectangle in the histogram for each row:
   • For each row, use a stack to maintain the indices of the histogram bars and calculate the largest rectangle area

Let's implement this solution in PHP: 85. Maximal Rectangle

<?php
function maximalRectangle($matrix) {
    if (empty($matrix) || empty($matrix[0])) {
        return 0;
    }

    $rows = count($matrix);
    $cols = count($matrix[0]);
    
    // Create a height array for histogram
    $height = array_fill(0, $cols, 0);
    $maxArea = 0;

    for ($i = 0; $i < $rows; $i++) {
        // Update height array
        for ($j = 0; $j < $cols; $j++) {
            $height[$j] = $matrix[$i][$j] == '1' ? $height[$j] + 1 : 0;
        }

        // Calculate the max area for this row's histogram
        $maxArea = max($maxArea, calculateMaxHistogramArea($height));
    }

    return $maxArea;
}

function calculateMaxHistogramArea($heights) {
    $stack = array();
    $maxArea = 0;
    $index = 0;

    while ($index < count($heights)) {
        if (empty($stack) || $heights[$index] >= $heights[end($stack)]) {
            array_push($stack, $index++);
        } else {
            $topOfStack = array_pop($stack);
            $area = $heights[$topOfStack] * (empty($stack) ? $index : $index - end($stack) - 1);
            $maxArea = max($maxArea, $area);
        }
    }

    while (!empty($stack)) {
        $topOfStack = array_pop($stack);
        $area = $heights[$topOfStack] * (empty($stack) ? $index : $index - end($stack) - 1);
        $maxArea = max($maxArea, $area);
    }

    return $maxArea;
}

// Test cases
$matrix1 = array(
    array("1","0","1","0","0"),
    array("1","0","1","1","1"),
    array("1","1","1","1","1"),
    array("1","0","0","1","0")
);

$matrix2 = array(
    array("0")
);

$matrix3 = array(
    array("1")
);

echo maximalRectangle($matrix1) . "\n"; // Output: 6
echo maximalRectangle($matrix2) . "\n"; // Output: 0
echo maximalRectangle($matrix3) . "\n"; // Output: 1

?>

Explanation:

1. Matrix Initialization:

   • If the matrix is empty or the first row is empty, return 0.

2. Height Array:

   • Initialize a height array that keeps track of the height of '1's for each column.

3. Updating Heights:

   • Traverse each row of the matrix and update the height of each column based on whether the matrix value is '1'.

4. Histogram Calculation:

   • For each updated height array, calculate the maximal rectangle area using a stack-based approach. This approach computes the maximum area for a histogram efficiently.

5. Stack-Based Histogram Calculation:

   • Use a stack to keep track of indices of increasing heights.
   • Calculate area whenever a decrease in height is detected and update the maximum area.

The calculateMaxHistogramArea function computes the largest rectangle area in a histogram, which is used to update the maximum area for each row's histogram. This approach ensures that the overall complexity is manageable given the problem constraints.

[basharul-siddike]

Thanks to solve the problem of comparing two version numbers