85. Maximal Rectangle – Leetcode Solutions

June 25, 2024

Table of Contents

Description:

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.

Examples:

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

Solution in Python:

To solve the problem of finding the largest rectangle containing only 1’s in a binary matrix, we can use a dynamic programming approach combined with the largest rectangle in histogram algorithm.

Python

from typing import List

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

        # Initialize the dimensions of the matrix
        rows, cols = len(matrix), len(matrix[0])
        # Initialize the height array
        heights = [0] * cols
        # Variable to store the maximum area
        max_area = 0

        # Iterate over each row in the matrix
        for row in matrix:
            for j in range(cols):
                # Update the height array
                if row[j] == '1':
                    heights[j] += 1
                else:
                    heights[j] = 0
            
            # Update the maximum area using the largest rectangle in histogram method
            max_area = max(max_area, self.largestRectangleArea(heights))

        return max_area

    def largestRectangleArea(self, heights: List[int]) -> int:
        # Stack to store the indices of the histogram bars
        stack = []
        # Variable to store the maximum area
        max_area = 0
        # Append a zero height to ensure we process all elements in the stack by the end
        heights.append(0)
        
        # Iterate over each height in the histogram
        for i in range(len(heights)):
            # While the current bar is shorter than the last one in the stack
            while stack and heights[i] < heights[stack[-1]]:
                # Pop the height from the stack
                h = heights[stack.pop()]
                # Calculate the width as the distance between the current index and the index
                # of the new top of the stack, minus one (if stack is not empty, else i)
                w = i if not stack else i - stack[-1] - 1
                # Update the maximum area
                max_area = max(max_area, h * w)
            # Push the current index onto the stack
            stack.append(i)
        
        # Remove the appended zero
        heights.pop()
        
        return max_area

Explanation:

Edge Case Handling:
- Check if the matrix or the first row is empty. If either is empty, return 0 as there’s no rectangle possible.
Height Array Initialization:
- Initialize a heights array with the same number of columns as the matrix, filled with 0’s. This array will be used to store the heights of histogram bars for each column.
Row-wise Histogram Update:
- Iterate over each row in the matrix. For each element in the row, update the corresponding value in the heights array:
  - If the element is ‘1’, increase the height by 1.
  - If the element is ‘0’, reset the height to 0.
Calculate Maximum Area for Each Row:
- After updating the heights array for the current row, call the largestRectangleArea method to calculate the maximum rectangular area for the current histogram.
- Update the max_area variable with the maximum value returned from this method.
Largest Rectangle in Histogram Calculation:
- This method uses a stack-based approach to find the largest rectangle in a histogram, similar to the solution explained previously for the largest rectangle problem in a histogram.
Stack-based Calculation:
- Use a stack to store the indices of the histogram bars.
- Iterate over the heights array. For each height, if the current height is less than the height of the bar at the index stored at the stack’s top, calculate the area of the rectangle ending at the bar corresponding to the top index of the stack.
- Update the maximum area accordingly.
- Push the current index onto the stack.

By combining these approaches, we can efficiently calculate the largest rectangle containing only 1’s in the given binary matrix.

Solution in Javascript:

JavaScript

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalRectangle = function(matrix) {
    if (!matrix || matrix.length === 0 || matrix[0].length === 0) {
        return 0;
    }

    // Initialize the dimensions of the matrix
    const rows = matrix.length;
    const cols = matrix[0].length;
    // Initialize the height array
    const heights = new Array(cols).fill(0);
    // Variable to store the maximum area
    let maxArea = 0;

    // Iterate over each row in the matrix
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            // Update the height array
            if (matrix[i][j] === '1') {
                heights[j] += 1;
            } else {
                heights[j] = 0;
            }
        }
        // Update the maximum area using the largest rectangle in histogram method
        maxArea = Math.max(maxArea, largestRectangleArea(heights));
    }

    return maxArea;
};

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
    // Stack to store the indices of the histogram bars
    const stack = [];
    // Variable to store the maximum area
    let maxArea = 0;
    // Append a zero height to ensure we process all elements in the stack by the end
    heights.push(0);

    // Iterate over each height in the histogram
    for (let i = 0; i < heights.length; i++) {
        // While the current bar is shorter than the last one in the stack
        while (stack.length > 0 && heights[i] < heights[stack[stack.length - 1]]) {
            // Pop the height from the stack
            const h = heights[stack.pop()];
            // Calculate the width as the distance between the current index and the index
            // of the new top of the stack, minus one (if stack is not empty, else i)
            const w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
            // Update the maximum area
            maxArea = Math.max(maxArea, h * w);
        }
        // Push the current index onto the stack
        stack.push(i);
    }

    // Remove the appended zero
    heights.pop();

    return maxArea;
};

Solution in Java:

Java

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        // Initialize the dimensions of the matrix
        int rows = matrix.length;
        int cols = matrix[0].length;
        // Initialize the height array
        int[] heights = new int[cols];
        // Variable to store the maximum area
        int maxArea = 0;

        // Iterate over each row in the matrix
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // Update the height array
                if (matrix[i][j] == '1') {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }
            }
            // Update the maximum area using the largest rectangle in histogram method
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }

        return maxArea;
    }

    private int largestRectangleArea(int[] heights) {
        // Stack to store the indices of the histogram bars
        Stack<Integer> stack = new Stack<>();
        // Variable to store the maximum area
        int maxArea = 0;
        // Append a zero height to ensure we process all elements in the stack by the end
        int[] extendedHeights = Arrays.copyOf(heights, heights.length + 1);

        // Iterate over each height in the histogram
        for (int i = 0; i < extendedHeights.length; i++) {
            // While the current bar is shorter than the last one in the stack
            while (!stack.isEmpty() && extendedHeights[i] < extendedHeights[stack.peek()]) {
                // Pop the height from the stack
                int h = extendedHeights[stack.pop()];
                // Calculate the width as the distance between the current index and the index
                // of the new top of the stack, minus one (if stack is not empty, else i)
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                // Update the maximum area
                maxArea = Math.max(maxArea, h * w);
            }
            // Push the current index onto the stack
            stack.push(i);
        }

        return maxArea;
    }
}

Solution in C#:

C#

using System;
using System.Collections.Generic;

public class Solution {
    public int MaximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.Length == 0 || matrix[0].Length == 0) {
            return 0;
        }

        // Initialize the dimensions of the matrix
        int rows = matrix.Length;
        int cols = matrix[0].Length;
        // Initialize the height array
        int[] heights = new int[cols];
        // Variable to store the maximum area
        int maxArea = 0;

        // Iterate over each row in the matrix
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // Update the height array
                if (matrix[i][j] == '1') {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }
            }
            // Update the maximum area using the largest rectangle in histogram method
            maxArea = Math.Max(maxArea, LargestRectangleArea(heights));
        }

        return maxArea;
    }

    private int LargestRectangleArea(int[] heights) {
        // Stack to store the indices of the histogram bars
        Stack<int> stack = new Stack<int>();
        // Variable to store the maximum area
        int maxArea = 0;
        // Append a zero height to ensure we process all elements in the stack by the end
        int[] extendedHeights = new int[heights.Length + 1];
        Array.Copy(heights, extendedHeights, heights.Length);
        extendedHeights[heights.Length] = 0;

        // Iterate over each height in the histogram
        for (int i = 0; i < extendedHeights.Length; i++) {
            // While the current bar is shorter than the last one in the stack
            while (stack.Count > 0 && extendedHeights[i] < extendedHeights[stack.Peek()]) {
                // Pop the height from the stack
                int h = extendedHeights[stack.Pop()];
                // Calculate the width as the distance between the current index and the index
                // of the new top of the stack, minus one (if stack is not empty, else i)
                int w = stack.Count == 0 ? i : i - stack.Peek() - 1;
                // Update the maximum area
                maxArea = Math.Max(maxArea, h * w);
            }
            // Push the current index onto the stack
            stack.Push(i);
        }

        return maxArea;
    }
}

85. Maximal Rectangle – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Popular

164. Maximum Gap – Leetcode Solutions

Lists (list). List functions and methods in Python

154. Find Minimum in Rotated Sorted Array II – Leetcode Solutions

12. Integer to Roman – Leetcode Solutions

283. Move Zeroes – Leetcode Solutions

89. Gray Code – Leetcode Solutions

221. Maximal Square – Leetcode Solutions

85. Maximal Rectangle – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Related Post

Popular