We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximal Rectangle

Number: 85

Difficulty: Hard

Paid? No

Companies: Google, Amazon, Microsoft, Meta, Bloomberg, TikTok, Apple, Oracle, Uber, DE Shaw, EPAM Systems

Problem 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. The solution must account for all matrix cells and efficiently compute the maximal area.

Key Insights

  • Transform each row into a histogram, where the height at each column is the count of consecutive '1's encountered so far.
  • Use a monotonic stack algorithm to compute the largest rectangle area within this histogram.
  • Iterate row by row, updating histogram heights and computing the maximal area based on the updated histogram.
  • This reduces a 2D problem into repeatedly solving the Largest Rectangle in Histogram problem.

Space and Time Complexity

Time Complexity: O(m*n), where m is the number of rows and n is the number of columns, since each histogram is processed in O(n) for each row. Space Complexity: O(n), needed for the histogram and the stack used in the algorithm.

Solution

The algorithm works by processing each row of the matrix and updating a histogram that represents the number of consecutive '1's for each column up to that row. For every row, we compute the largest rectangle area in the histogram by using a monotonic stack:

  1. Iterate through each column index in the histogram.
  2. Use a stack to store column indices such that the heights are in non-decreasing order.
  3. When a height less than the current height is encountered, pop indices from the stack and calculate the area using the height at the popped index and the current index as the right boundary.
  4. After processing, ensure remaining indices in the stack are handled.
  5. The maximum area found over all rows is returned as the answer.

Code Solutions

# Python solution for Maximal Rectangle

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        
        # Number of columns
        n = len(matrix[0])
        # Initialize histogram heights with 0's
        heights = [0] * n
        max_area = 0
        
        # Process each row in the matrix
        for row in matrix:
            for i in range(n):
                # Update histogram: increase height if '1' else reset to 0
                if row[i] == '1':
                    heights[i] += 1
                else:
                    heights[i] = 0
            
            # Calculate maximal area for the current histogram row
            max_area = max(max_area, self.largestRectangleArea(heights))
        
        return max_area

    def largestRectangleArea(self, heights: List[int]) -> int:
        # Append a zero at the end for flush-out
        heights.append(0)
        stack = []
        max_area = 0
        
        # Process every bar in the histogram
        for i, h in enumerate(heights):
            # Maintain stack in non-decreasing order of heights
            while stack and heights[stack[-1]] > h:
                height = heights[stack.pop()]
                # Determine width of the rectangle
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)
        
        # Remove the appended 0 
        heights.pop()
        return max_area
← Back to All Questions