Solution Approach
Solution Overview
There are 2 main approaches to solve this problem:
- Histogram Approach - Complex approach
- Dynamic Programming Approach - Complex approach
Approach 1: Histogram Approach
The key insight for solving this problem efficiently is to transform it into a series of "largest rectangle in histogram" problems. For each row in the matrix, we can calculate the height of the histogram at each position (how many consecutive 1's are above the current position, including the current position).
Once we have the heights for a row, we can use a stack-based algorithm to find the largest rectangle in that histogram. We repeat this process for each row and keep track of the maximum area found.
Algorithm:
- For each row in the matrix:
- Calculate the height of the histogram at each position (number of consecutive 1's above, including current position).
- If the current cell is '0', the height is reset to 0.
- If the current cell is '1', the height is incremented by 1 from the height in the previous row.
- Use a stack-based algorithm to find the largest rectangle in the histogram for the current row.
- Keep track of the maximum area found across all rows.
Time Complexity:
Where m is the number of rows and n is the number of columns in the matrix. We process each cell once to build the histograms, and the stack-based algorithm for finding the largest rectangle in a histogram is O(n) for each row.
Space Complexity:
We need O(n) space to store the heights for the current row and O(n) space for the stack used in the histogram algorithm.
Approach 2: Dynamic Programming Approach
We can also solve this problem using dynamic programming by maintaining three arrays for each position: height (same as in the histogram approach), left (the leftmost position where the rectangle can extend), and right (the rightmost position where the rectangle can extend).
For each position, we calculate these values and then compute the area of the largest rectangle that can be formed with the current position as the bottom-most row.
Algorithm:
- Initialize three arrays: height, left, and right, each of size n (number of columns).
- For each row in the matrix:
- Update the height array: If the current cell is '1', increment the height; otherwise, reset it to 0.
- Update the left array: Find the leftmost position where the rectangle can extend horizontally.
- Update the right array: Find the rightmost position where the rectangle can extend horizontally.
- Calculate the area for each position: (right[j] - left[j]) * height[j].
- Keep track of the maximum area found.
Time Complexity:
Where m is the number of rows and n is the number of columns in the matrix. We process each cell once and perform constant-time operations for each cell.
Space Complexity:
We need three arrays of size n to store the height, left, and right values for the current row.
Pseudocode
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849function maximalRectangle(matrix): if matrix is empty: return 0 m = number of rows in matrix n = number of columns in matrix heights = array of size n, initialized with 0s maxArea = 0 for i from 0 to m-1: // Update heights for current row for j from 0 to n-1: if matrix[i][j] == '1': heights[j] += 1 else: heights[j] = 0 // Find largest rectangle in current histogram maxArea = max(maxArea, largestRectangleInHistogram(heights)) return maxArea function largestRectangleInHistogram(heights): stack = empty stack maxArea = 0 i = 0 while i < length of heights: // If stack is empty or current height is >= height at stack top, push to stack if stack is empty or heights[i] >= heights[stack.top()]: stack.push(i) i++ else: // Pop the stack and calculate area with the popped height as the limiting height top = stack.pop() // Calculate width based on stack width = i if stack is empty else i - stack.top() - 1 // Update max area maxArea = max(maxArea, heights[top] * width) // Process remaining elements in stack while stack is not empty: top = stack.pop() width = i if stack is empty else i - stack.top() - 1 maxArea = max(maxArea, heights[top] * width) return maxAreaString Problems
Learning Objective
Understand different approaches to solve the maximal rectangle problem and analyze their efficiency.
Solution Approaches
Approach 1: Histogram Approach
The key insight for solving this problem efficiently is to transform it into a series of "largest rectangle in histogram" problems. For each row in the matrix, we can calculate the height of the histogram at each position (how many consecutive 1's are above the current position, including the current position).
Once we have the heights for a row, we can use a stack-based algorithm to find the largest rectangle in that histogram. We repeat this process for each row and keep track of the maximum area found.
Algorithm:
- For each row in the matrix:
- Calculate the height of the histogram at each position (number of consecutive 1's above, including current position).
- If the current cell is '0', the height is reset to 0.
- If the current cell is '1', the height is incremented by 1 from the height in the previous row.
- Use a stack-based algorithm to find the largest rectangle in the histogram for the current row.
- Keep track of the maximum area found across all rows.
Approach 2: Dynamic Programming Approach
We can also solve this problem using dynamic programming by maintaining three arrays for each position: height (same as in the histogram approach), left (the leftmost position where the rectangle can extend), and right (the rightmost position where the rectangle can extend).
For each position, we calculate these values and then compute the area of the largest rectangle that can be formed with the current position as the bottom-most row.
Algorithm:
- Initialize three arrays: height, left, and right, each of size n (number of columns).
- For each row in the matrix:
- Update the height array: If the current cell is '1', increment the height; otherwise, reset it to 0.
- Update the left array: Find the leftmost position where the rectangle can extend horizontally.
- Update the right array: Find the rightmost position where the rectangle can extend horizontally.
- Calculate the area for each position: (right[j] - left[j]) * height[j].
- Keep track of the maximum area found.
Complexity Analysis
Histogram Approach Approach
Time Complexity
Where m is the number of rows and n is the number of columns in the matrix. We process each cell once to build the histograms, and the stack-based algorithm for finding the largest rectangle in a histogram is O(n) for each row.
Space Complexity
We need O(n) space to store the heights for the current row and O(n) space for the stack used in the histogram algorithm.
Dynamic Programming Approach Approach
Time Complexity
Where m is the number of rows and n is the number of columns in the matrix. We process each cell once and perform constant-time operations for each cell.
Space Complexity
We need three arrays of size n to store the height, left, and right values for the current row.
Pseudocode
Histogram Approach Approach
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849function maximalRectangle(matrix): if matrix is empty: return 0 m = number of rows in matrix n = number of columns in matrix heights = array of size n, initialized with 0s maxArea = 0 for i from 0 to m-1: // Update heights for current row for j from 0 to n-1: if matrix[i][j] == '1': heights[j] += 1 else: heights[j] = 0 // Find largest rectangle in current histogram maxArea = max(maxArea, largestRectangleInHistogram(heights)) return maxArea function largestRectangleInHistogram(heights): stack = empty stack maxArea = 0 i = 0 while i < length of heights: // If stack is empty or current height is >= height at stack top, push to stack if stack is empty or heights[i] >= heights[stack.top()]: stack.push(i) i++ else: // Pop the stack and calculate area with the popped height as the limiting height top = stack.pop() // Calculate width based on stack width = i if stack is empty else i - stack.top() - 1 // Update max area maxArea = max(maxArea, heights[top] * width) // Process remaining elements in stack while stack is not empty: top = stack.pop() width = i if stack is empty else i - stack.top() - 1 maxArea = max(maxArea, heights[top] * width) return maxAreaDynamic Programming Approach Approach
12345678910111213141516171819202122232425262728293031323334353637383940414243function maximalRectangle(matrix): if matrix is empty: return 0 m = number of rows in matrix n = number of columns in matrix height = array of size n, initialized with 0s left = array of size n, initialized with 0s right = array of size n, initialized with n maxArea = 0 for i from 0 to m-1: currentLeft = 0 currentRight = n // Update height for j from 0 to n-1: if matrix[i][j] == '1': height[j] += 1 else: height[j] = 0 // Update left for j from 0 to n-1: if matrix[i][j] == '1': left[j] = max(left[j], currentLeft) else: left[j] = 0 currentLeft = j + 1 // Update right for j from n-1 to 0: if matrix[i][j] == '1': right[j] = min(right[j], currentRight) else: right[j] = n currentRight = j // Calculate area for j from 0 to n-1: maxArea = max(maxArea, (right[j] - left[j]) * height[j]) return maxArea