Problem Statement
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
Try here before watching the video.
Video Solution
Java Code
class Solution {
public int maximalRectangle(char[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] bars = new int[m][n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(i == 0) {
bars[i][j] = matrix[i][j] - '0';
} else if(matrix[i][j] == '0') {
bars[i][j] = 0;
} else {
bars[i][j] = bars[i - 1][j] + 1;
}
}
}
int res = 0;
for(int i = 0; i < m; i++) {
res = Math.max(res, findArea(bars[i]));
}
return res;
}
int findArea(int[] bar) {
int[] ngel = nextGreaterElementToLeft(bar);
int[] nger = nextGreaterElementToRight(bar);
int res = 0;
for(int i = 0; i < bar.length; i++) {
res = Math.max(res, (nger[i] - ngel[i] - 1) * bar[i]);
}
return res;
}
int[] nextGreaterElementToLeft(int[] bar) {
Stack<int[]> stack = new Stack<>();
int[] ngel = new int[bar.length];
for(int i = 0; i < bar.length; i++) {
while(!stack.isEmpty() && stack.peek()[0] >= bar[i]) {
stack.pop();
}
if(stack.isEmpty()) {
ngel[i] = -1;
} else {
ngel[i] = stack.peek()[1];
}
int[] arr = new int[2];
arr[0] = bar[i];
arr[1] = i;
stack.push(arr);
}
return ngel;
}
int[] nextGreaterElementToRight(int[] bar) {
Stack<int[]> stack = new Stack<>();
int nger[] = new int[bar.length];
for(int i = bar.length - 1; i >= 0; i--) {
while(!stack.isEmpty() && stack.peek()[0] >= bar[i]) {
stack.pop();
}
if(stack.isEmpty()) {
nger[i] = bar.length;
} else {
nger[i] = stack.peek()[1];
}
int[] arr = new int[2];
arr[0] = bar[i];
arr[1] = i;
stack.push(arr);
}
return nger;
}
}
C++ Code
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
std::vector<std::vector<int>> bars(m, std::vector<int>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0) {
bars[i][j] = matrix[i][j] - '0';
} else if (matrix[i][j] == '0') {
bars[i][j] = 0;
} else {
bars[i][j] = bars[i - 1][j] + 1;
}
}
}
int res = 0;
for (int i = 0; i < m; i++) {
res = std::max(res, findArea(bars[i]));
}
return res;
}
int findArea(std::vector<int>& bar) {
std::vector<int> ngel = nextGreaterElementToLeft(bar);
std::vector<int> nger = nextGreaterElementToRight(bar);
int res = 0;
for (int i = 0; i < bar.size(); i++) {
res = std::max(res, (nger[i] - ngel[i] - 1) * bar[i]);
}
return res;
}
std::vector<int> nextGreaterElementToLeft(std::vector<int>& bar) {
std::stack<std::pair<int, int>> stack;
std::vector<int> ngel(bar.size(), -1);
for (int i = 0; i < bar.size(); i++) {
while (!stack.empty() && stack.top().first >= bar[i]) {
stack.pop();
}
if (!stack.empty()) {
ngel[i] = stack.top().second;
}
stack.push({bar[i], i});
}
return ngel;
}
std::vector<int> nextGreaterElementToRight(std::vector<int>& bar) {
std::stack<std::pair<int, int>> stack;
std::vector<int> nger(bar.size(), bar.size());
for (int i = bar.size() - 1; i >= 0; i--) {
while (!stack.empty() && stack.top().first >= bar[i]) {
stack.pop();
}
if (!stack.empty()) {
nger[i] = stack.top().second;
}
stack.push({bar[i], i});
}
return nger;
}
};
Python Code
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
m, n = len(matrix), len(matrix[0])
bars = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if i == 0:
bars[i][j] = int(matrix[i][j])
elif matrix[i][j] == '0':
bars[i][j] = 0
else:
bars[i][j] = bars[i - 1][j] + 1
res = 0
for i in range(m):
res = max(res, self.findArea(bars[i]))
return res
def findArea(self, bar: List[int]) -> int:
ngel = self.nextGreaterElementToLeft(bar)
nger = self.nextGreaterElementToRight(bar)
res = 0
for i in range(len(bar)):
res = max(res, (nger[i] - ngel[i] - 1) * bar[i])
return res
def nextGreaterElementToLeft(self, bar: List[int]) -> List[int]:
stack = []
ngel = [-1] * len(bar)
for i in range(len(bar)):
while stack and stack[-1][0] >= bar[i]:
stack.pop()
if stack:
ngel[i] = stack[-1][1]
stack.append((bar[i], i))
return ngel
def nextGreaterElementToRight(self, bar: List[int]) -> List[int]:
stack = []
nger = [len(bar)] * len(bar)
for i in range(len(bar) - 1, -1, -1):
while stack and stack[-1][0] >= bar[i]:
stack.pop()
if stack:
nger[i] = stack[-1][1]
stack.append((bar[i], i))
return nger
Javascript Code
/**
* @param {character[][]} matrix
* @return {number}
*/
var maximalRectangle = function(matrix) {
const m = matrix.length;
if (m === 0) return 0;
const n = matrix[0].length;
if (n === 0) return 0;
const bars = [];
for (let i = 0; i < m; i++) {
bars.push(new Array(n).fill(0));
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (i === 0) {
bars[i][j] = parseInt(matrix[i][j]);
} else if (matrix[i][j] === '0') {
bars[i][j] = 0;
} else {
bars[i][j] = bars[i - 1][j] + 1;
}
}
}
let res = 0;
for (let i = 0; i < m; i++) {
res = Math.max(res, findArea(bars[i]));
}
return res;
function findArea(bar) {
const ngel = nextGreaterElementToLeft(bar);
const nger = nextGreaterElementToRight(bar);
let res = 0;
for (let i = 0; i < bar.length; i++) {
res = Math.max(res, (nger[i] - ngel[i] - 1) * bar[i]);
}
return res;
}
function nextGreaterElementToLeft(bar) {
const stack = [];
const ngel = Array(bar.length).fill(-1);
for (let i = 0; i < bar.length; i++) {
while (stack.length && stack[stack.length - 1][0] >= bar[i]) {
stack.pop();
}
if (stack.length) {
ngel[i] = stack[stack.length - 1][1];
}
stack.push([bar[i], i]);
}
return ngel;
}
function nextGreaterElementToRight(bar) {
const stack = [];
const nger = Array(bar.length).fill(bar.length);
for (let i = bar.length - 1; i >= 0; i--) {
while (stack.length && stack[stack.length - 1][0] >= bar[i]) {
stack.pop();
}
if (stack.length) {
nger[i] = stack[stack.length - 1][1];
}
stack.push([bar[i], i]);
}
return nger;
}
};
Go Code
func maximalRectangle(matrix [][]byte) int {
m := len(matrix)
if m == 0 {
return 0
}
n := len(matrix[0])
if n == 0 {
return 0
}
bars := make([][]int, m)
for i := range bars {
bars[i] = make([]int, n)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if i == 0 {
bars[i][j] = int(matrix[i][j] - '0')
} else if matrix[i][j] == '0' {
bars[i][j] = 0
} else {
bars[i][j] = bars[i-1][j] + 1
}
}
}
res := 0
for i := 0; i < m; i++ {
res = max(res, findArea(bars[i]))
}
return res
}
func findArea(bar []int) int {
ngel := nextGreaterElementToLeft(bar)
nger := nextGreaterElementToRight(bar)
res := 0
for i := 0; i < len(bar); i++ {
res = max(res, (nger[i]-ngel[i]-1)*bar[i])
}
return res
}
func nextGreaterElementToLeft(bar []int) []int {
stack := [][]int{}
ngel := make([]int, len(bar))
for i := 0; i < len(bar); i++ {
for len(stack) > 0 && stack[len(stack)-1][0] >= bar[i] {
stack = stack[:len(stack)-1]
}
if len(stack) == 0 {
ngel[i] = -1
} else {
ngel[i] = stack[len(stack)-1][1]
}
stack = append(stack, []int{bar[i], i})
}
return ngel
}
func nextGreaterElementToRight(bar []int) []int {
stack := [][]int{}
nger := make([]int, len(bar))
for i := len(bar) - 1; i >= 0; i-- {
for len(stack) > 0 && stack[len(stack)-1][0] >= bar[i] {
stack = stack[:len(stack)-1]
}
if len(stack) == 0 {
nger[i] = len(bar)
} else {
nger[i] = stack[len(stack)-1][1]
}
stack = append(stack, []int{bar[i], i})
}
return nger
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Complexity Analysis
Time Complexity: O(M*N)
Space Complexity: O(M*N)