Last updated on October 9th, 2024 at 10:16 pm

Here, We see Maximal Rectangle LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Maximal Rectangle LeetCode Solution

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

Example 3:

Input: matrix = [["1"]]
Output: 1

1. Maximal Rectangle Leetcode Solution C++

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int m = matrix.size(), n = matrix[0].size(), res = 0;
        vector<int> heights(n, 0);
        for (int i = 0; i < m; ++i) {
            int ones = 0;
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '0') heights[j] = 0;
                else {
                    ++ones;
                    ++heights[j];
                }
            }
            if (ones > 0) res = max(res, maxArea(heights));  // if all 0s in the row, no need to call the function
        }
        return res;
    }
    int maxArea(vector<int>& heights) { // copy paste from problem 84
        int n = heights.size(), area = 0, h = 0, l = 0;
        stack<int> stk;
        for (int i = 0; i <= n; ++i) {
            while(!stk.empty() && (i == n || heights[stk.top()] > heights[i])) {
                h = heights[stk.top()]; stk.pop();
                l = stk.empty() ? -1 : stk.top();
                area = max(area, h * (i - 1 - l));
            }
            stk.push(i);
        }
        return area;     
    }
};

2. Maximal Rectangle Leetcode Solution Java

class Solution {
    public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0) return 0;
    int ans = 0, m = matrix.length, n = matrix[0].length;
    int[] height = new int[n]; // height

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == '0') {
                height[j] = 0;
                continue;
            }
            height[j]++;
            for (int cur = j - 1, pre = height[j]; cur >= 0; cur--) {
                if (height[cur] == 0) break;
                pre = Math.min(pre, height[cur]);
                ans = Math.max(ans, (j - cur + 1) * pre);
            }
            ans = Math.max(ans, height[j]);
        }
    }
    return ans;        
    }
}

3. Maximal Rectangle Leetcode Solution JavaScript

var maximalRectangle = function(matrix) {
    const n = matrix.length;
    if (n === 0) return 0;
    const m = matrix[0].length;

    const h = new Array(n).fill(0);

    let max = 0;
    for (let j = 0; j < m; j++) {
        for (let i = 0; i < n; i++) {
            if (matrix[i][j] === '1') h[i]++;
            else h[i] = 0;
        }
        for (let i = 0; i < n; i++) {
            let k1 = i - 1;
            while (k1 >= 0 && h[i] <= h[k1]) k1--;
            let k2 = i + 1;
            while (k2 < n && h[i] <= h[k2]) k2++;
            max = Math.max(max, h[i] * (k2 - k1 - 1));
        }
    }
    return max;    
};

4. Maximal Rectangle Leetcode Solution Python

class Solution(object):
    def maximalRectangle(self, matrix):
        maxVal = 0
        out = 0
        if matrix==[]:
            return 0
        minWidth = defaultdict(lambda: defaultdict(int))
        for di in range(len(matrix)):
            currW = len(matrix[0])
            for dj in range(len(matrix[0])-1, -1, -1):
                if matrix[di][dj] != "1":
                    minWidth[di][dj] = 0
                else:
                    minWidth[di][dj] = 1
                    minWidth[di][dj] += minWidth[di][dj+1] if dj+1!=len(matrix[0]) else 0
					
        maxArea = 0
        for j in range(len(matrix[0])):
            maxLeft = [-1]*len(matrix)
            maxRight = [len(matrix)]*len(matrix)
            stack = []
            for i in range(len(matrix)):
                while stack and minWidth[i][j] < minWidth[stack[-1]][j]:
                    maxRight[stack.pop()] = i
                maxLeft[i] = stack[-1] if stack else -1
                stack.append(i)
            area = [(maxRight[i] - maxLeft[i] - 1)*minWidth[i][j] for i in range(len(matrix))]
            maxArea = max(maxArea, max(area))
        return maxArea