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.lengthcols == matrix[i].length1 <= row, cols <= 200matrix[i][j]is'0'or'1'.
Approach 01
-
C++
-
Python
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> NSR(vector<int>& heights) {
stack<int> st;
int n = heights.size();
int pseudo_index = n;
vector<int> right(n);
for(int i = n-1; i>=0; i--) {
if(st.empty()) {
right[i] = pseudo_index;
} else {
while(!st.empty() && heights[st.top()] >= heights[i])
st.pop();
if(st.empty())
right[i] = pseudo_index;
else
right[i] = st.top();
}
st.push(i);
}
return right;
}
vector<int> NSL(vector<int>& heights) {
stack<int> st;
int n = heights.size();
int pseudo_index = -1;
vector<int> left(n);
for(int i = 0; i<n; i++) {
if(st.empty()) {
left[i] = pseudo_index;
} else {
while(!st.empty() && heights[st.top()] >= heights[i])
st.pop();
if(st.empty())
left[i] = pseudo_index;
else
left[i] = st.top();
}
st.push(i);
}
return left;
}
int MAH(vector<int>& heights) {
int n = heights.size();
vector<int> right = NSR(heights);
vector<int> left = NSL(heights);
vector<int> width(n);
for(int i = 0; i<n; i++)
width[i] = right[i]-left[i]-1;
int max_area = 0;
for(int i = 0; i<n; i++) {
int a = width[i]*heights[i];
if(max_area < a)
max_area = a;
}
return max_area;
}
int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.size() == 0)
return 0;
int n = matrix.size();
int m = matrix[0].size();
vector<int> height(m);
for(int i = 0; i<m; i++) {
height[i] = (matrix[0][i]=='1')?1:0;
}
int maxA = MAH(height);
for(int i = 1; i<n; i++) {
for(int j = 0; j<m; j++) {
if(matrix[i][j] == '0')
height[j] = 0;
else
height[j] += 1;
}
maxA = max(maxA, MAH(height));
}
return maxA;
}
};
from typing import *
class Solution:
def NSR(self, heights):
stack = []
n = len(heights)
pseudo_index = n
right = [pseudo_index] * n
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
if not stack:
right[i] = pseudo_index
else:
right[i] = stack[-1]
stack.append(i)
return right
def NSL(self, heights):
stack = []
n = len(heights)
pseudo_index = -1
left = [pseudo_index] * n
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
if not stack:
left[i] = pseudo_index
else:
left[i] = stack[-1]
stack.append(i)
return left
def MAH(self, heights):
n = len(heights)
right = self.NSR(heights)
left = self.NSL(heights)
width = [0] * n
for i in range(n):
width[i] = right[i] - left[i] - 1
max_area = 0
for i in range(n):
area = width[i] * heights[i]
max_area = max(max_area, area)
return max_area
def maximalRectangle(self, matrix):
if not matrix:
return 0
n = len(matrix)
m = len(matrix[0])
height = [0] * m
for i in range(m):
height[i] = 1 if matrix[0][i] == '1' else 0
max_area = self.MAH(height)
for row in range(1, n):
for col in range(m):
if matrix[row][col] == '0':
height[col] = 0
else:
height[col] += 1
max_area = max(max_area, self.MAH(height))
return max_area
Time Complexity
- NSR and NSL Functions:
Both
NSR(Next Smaller to Right) andNSL(Next Smaller to Left) functions involve iterating through the heights array and performing stack operations. Each element is pushed and popped from the stack at most once, so each function takes \( O(n) \) time. - MAH Function:
The
MAH(Maximum Area Histogram) function calls theNSRandNSLfunctions and performs additional operations on the heights array, taking \( O(n) \) time. - maximalRectangle Function:
The
maximalRectanglefunction iterates through each row of the matrix and calls theMAHfunction, resulting in a time complexity of \( O(n \cdot m) \), where \( n \) is the number of rows and \( m \) is the number of columns. - Overall Time Complexity:
The overall time complexity of the algorithm is \( O(n \cdot m) \).
Space Complexity
- NSR and NSL Functions:
Both
NSRandNSLfunctions use a stack and an array of size \( n \), resulting in \( O(n) \) space complexity. - MAH Function:
The
MAHfunction uses the space required by theNSRandNSLfunctions and additional arrays of size \( n \), resulting in \( O(n) \) space complexity. - maximalRectangle Function:
The
maximalRectanglefunction uses an array of size \( m \) to store the heights, resulting in \( O(m) \) space complexity. - Overall Space Complexity:
The overall space complexity of the algorithm is \( O(m) \) since the height array dominates the space usage.