Skip to content

85. Maximal Rectangle

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.

Β 

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.length
  • cols == matrix[i].length
  • 1 <= rows, cols <= 200
  • matrix[i][j] is '0' or '1'.

Solutions

Solution 1: Monotonic Stack

We can treat each row as the base of a histogram and calculate the maximum area of the histogram for each row.

Specifically, we maintain an array \(\textit{heights}\) with the same length as the number of columns in the matrix, where \(\textit{heights}[j]\) represents the height of the column at the \(j\)-th position with the current row as the base. For each row, we iterate through each column:

  • If the current element is '1', increment \(\textit{heights}[j]\) by \(1\).
  • If the current element is '0', set \(\textit{heights}[j]\) to \(0\).

Then, we use the monotonic stack algorithm to calculate the maximum rectangle area of the current histogram and update the answer.

The specific steps of the monotonic stack are as follows:

  1. Initialize an empty stack \(\textit{stk}\) to store the indices of the columns.
  2. Initialize two arrays \(\textit{left}\) and \(\textit{right}\), representing the index of the first column to the left and right of each column that is shorter than the current column.
  3. Iterate through the heights array \(\textit{heights}\), first calculating the index of the first column to the left of each column that is shorter than the current column, and store it in \(\textit{left}\).
  4. Then iterate through the heights array \(\textit{heights}\) in reverse order, calculating the index of the first column to the right of each column that is shorter than the current column, and store it in \(\textit{right}\).
  5. Finally, calculate the maximum rectangle area for each column and update the answer.

The time complexity is \(O(m \times n)\), where \(m\) is the number of rows in \(matrix\) and \(n\) is the number of columns in \(matrix\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        heights = [0] * len(matrix[0])
        ans = 0
        for row in matrix:
            for j, v in enumerate(row):
                if v == "1":
                    heights[j] += 1
                else:
                    heights[j] = 0
            ans = max(ans, self.largestRectangleArea(heights))
        return ans

    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        stk = []
        left = [-1] * n
        right = [n] * n
        for i, h in enumerate(heights):
            while stk and heights[stk[-1]] >= h:
                stk.pop()
            if stk:
                left[i] = stk[-1]
            stk.append(i)
        stk = []
        for i in range(n - 1, -1, -1):
            h = heights[i]
            while stk and heights[stk[-1]] >= h:
                stk.pop()
            if stk:
                right[i] = stk[-1]
            stk.append(i)
        return max(h * (right[i] - left[i] - 1) for i, h in enumerate(heights))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int maximalRectangle(char[][] matrix) {
        int n = matrix[0].length;
        int[] heights = new int[n];
        int ans = 0;
        for (var row : matrix) {
            for (int j = 0; j < n; ++j) {
                if (row[j] == '1') {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }
            }
            ans = Math.max(ans, largestRectangleArea(heights));
        }
        return ans;
    }

    private int largestRectangleArea(int[] heights) {
        int res = 0, n = heights.length;
        Deque<Integer> stk = new ArrayDeque<>();
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(right, n);
        for (int i = 0; i < n; ++i) {
            while (!stk.isEmpty() && heights[stk.peek()] >= heights[i]) {
                right[stk.pop()] = i;
            }
            left[i] = stk.isEmpty() ? -1 : stk.peek();
            stk.push(i);
        }
        for (int i = 0; i < n; ++i) {
            res = Math.max(res, heights[i] * (right[i] - left[i] - 1));
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix[0].size();
        vector<int> heights(n);
        int ans = 0;
        for (auto& row : matrix) {
            for (int j = 0; j < n; ++j) {
                if (row[j] == '1')
                    ++heights[j];
                else
                    heights[j] = 0;
            }
            ans = max(ans, largestRectangleArea(heights));
        }
        return ans;
    }

    int largestRectangleArea(vector<int>& heights) {
        int res = 0, n = heights.size();
        stack<int> stk;
        vector<int> left(n, -1);
        vector<int> right(n, n);
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && heights[stk.top()] >= heights[i]) {
                right[stk.top()] = i;
                stk.pop();
            }
            if (!stk.empty()) left[i] = stk.top();
            stk.push(i);
        }
        for (int i = 0; i < n; ++i)
            res = max(res, heights[i] * (right[i] - left[i] - 1));
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
func maximalRectangle(matrix [][]byte) int {
    n := len(matrix[0])
    heights := make([]int, n)
    ans := 0
    for _, row := range matrix {
        for j, v := range row {
            if v == '1' {
                heights[j]++
            } else {
                heights[j] = 0
            }
        }
        ans = max(ans, largestRectangleArea(heights))
    }
    return ans
}

func largestRectangleArea(heights []int) int {
    res, n := 0, len(heights)
    var stk []int
    left, right := make([]int, n), make([]int, n)
    for i := range right {
        right[i] = n
    }
    for i, h := range heights {
        for len(stk) > 0 && heights[stk[len(stk)-1]] >= h {
            right[stk[len(stk)-1]] = i
            stk = stk[:len(stk)-1]
        }
        if len(stk) > 0 {
            left[i] = stk[len(stk)-1]
        } else {
            left[i] = -1
        }
        stk = append(stk, i)
    }
    for i, h := range heights {
        res = max(res, h*(right[i]-left[i]-1))
    }
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
function maximalRectangle(matrix: string[][]): number {
    const n = matrix[0].length;
    const heights: number[] = new Array(n).fill(0);
    let ans = 0;

    for (const row of matrix) {
        for (let j = 0; j < n; ++j) {
            if (row[j] === '1') {
                heights[j] += 1;
            } else {
                heights[j] = 0;
            }
        }
        ans = Math.max(ans, largestRectangleArea(heights));
    }

    return ans;
}

function largestRectangleArea(heights: number[]): number {
    let res = 0;
    const n = heights.length;
    const stk: number[] = [];
    const left: number[] = new Array(n);
    const right: number[] = new Array(n).fill(n);

    for (let i = 0; i < n; ++i) {
        while (stk.length && heights[stk[stk.length - 1]] >= heights[i]) {
            right[stk.pop()!] = i;
        }
        left[i] = stk.length === 0 ? -1 : stk[stk.length - 1];
        stk.push(i);
    }

    for (let i = 0; i < n; ++i) {
        res = Math.max(res, heights[i] * (right[i] - left[i] - 1));
    }

    return res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
impl Solution {
    pub fn maximal_rectangle(matrix: Vec<Vec<char>>) -> i32 {
        let n = matrix[0].len();
        let mut heights = vec![0; n];
        let mut ans = 0;

        for row in matrix {
            for j in 0..n {
                if row[j] == '1' {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }
            }
            ans = ans.max(Self::largest_rectangle_area(&heights));
        }

        ans
    }

    fn largest_rectangle_area(heights: &Vec<i32>) -> i32 {
        let mut res = 0;
        let n = heights.len();
        let mut stk: Vec<usize> = Vec::new();
        let mut left = vec![0; n];
        let mut right = vec![n; n];

        for i in 0..n {
            while let Some(&top) = stk.last() {
                if heights[top] >= heights[i] {
                    right[top] = i;
                    stk.pop();
                } else {
                    break;
                }
            }
            left[i] = if stk.is_empty() { -1 } else { stk[stk.len() - 1] as i32 };
            stk.push(i);
        }

        for i in 0..n {
            res = res.max(heights[i] * (right[i] as i32 - left[i] - 1));
        }

        res
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Solution {
    public int MaximalRectangle(char[][] matrix) {
        int n = matrix[0].Length;
        int[] heights = new int[n];
        int ans = 0;

        foreach (var row in matrix) {
            for (int j = 0; j < n; ++j) {
                if (row[j] == '1') {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }
            }
            ans = Math.Max(ans, LargestRectangleArea(heights));
        }

        return ans;
    }

    private int LargestRectangleArea(int[] heights) {
        int res = 0, n = heights.Length;
        Stack<int> stk = new Stack<int>();
        int[] left = new int[n];
        int[] right = new int[n];

        Array.Fill(right, n);

        for (int i = 0; i < n; ++i) {
            while (stk.Count > 0 && heights[stk.Peek()] >= heights[i]) {
                right[stk.Pop()] = i;
            }
            left[i] = stk.Count == 0 ? -1 : stk.Peek();
            stk.Push(i);
        }

        for (int i = 0; i < n; ++i) {
            res = Math.Max(res, heights[i] * (right[i] - left[i] - 1));
        }

        return res;
    }
}

Comments