85. Maximal Rectangle LeetCode Solution

In this guide, you will get 85. Maximal Rectangle LeetCode Solution with the best time and space complexity. The solution to Maximal Rectangle problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximal Rectangle solution in C++
Maximal Rectangle solution in Java
Maximal Rectangle solution in Python
Additional Resources

85. Maximal Rectangle LeetCode Solution image

Problem Statement of Maximal Rectangle

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

Complexity Analysis

Time Complexity: O(mn)
Space Complexity: O(n)

85. Maximal Rectangle LeetCode Solution in C++

class Solution {
 public:
  int maximalRectangle(vector<vector<char>>& matrix) {
    if (matrix.empty())
      return 0;

    int ans = 0;
    vector<int> hist(matrix[0].size());

    for (const vector<char>& row : matrix) {
      for (int i = 0; i < row.size(); ++i)
        hist[i] = row[i] == '0' ? 0 : hist[i] + 1;
      ans = max(ans, largestRectangleArea(hist));
    }

    return ans;
  }

 private:
  int largestRectangleArea(const vector<int>& heights) {
    int ans = 0;
    stack<int> stack;

    for (int i = 0; i <= heights.size(); ++i) {
      while (!stack.empty() &&
             (i == heights.size() || heights[stack.top()] > heights[i])) {
        const int h = heights[stack.top()];
        stack.pop();
        const int w = stack.empty() ? i : i - stack.top() - 1;
        ans = max(ans, h * w);
      }
      stack.push(i);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

85. Maximal Rectangle LeetCode Solution in Java

class Solution {
  public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0)
      return 0;

    int ans = 0;
    int[] hist = new int[matrix[0].length];

    for (char[] row : matrix) {
      for (int i = 0; i < row.length; ++i)
        hist[i] = row[i] == '0' ? 0 : hist[i] + 1;
      ans = Math.max(ans, largestRectangleArea(hist));
    }

    return ans;
  }

  private int largestRectangleArea(int[] heights) {
    int ans = 0;
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i <= heights.length; ++i) {
      while (!stack.isEmpty() && (i == heights.length || heights[stack.peek()] > heights[i])) {
        final int h = heights[stack.pop()];
        final int w = stack.isEmpty() ? i : i - stack.peek() - 1;
        ans = Math.max(ans, h * w);
      }
      stack.push(i);
    }

    return ans;
  }
}
// code provided by PROGIEZ

85. Maximal Rectangle LeetCode Solution in Python

class Solution:
  def maximalRectangle(self, matrix: list[list[str]]) -> int:
    if not matrix:
      return 0

    ans = 0
    hist = [0] * len(matrix[0])

    def largestRectangleArea(heights: list[int]) -> int:
      ans = 0
      stack = []

      for i in range(len(heights) + 1):
        while stack and (i == len(heights) or heights[stack[-1]] > heights[i]):
          h = heights[stack.pop()]
          w = i - stack[-1] - 1 if stack else i
          ans = max(ans, h * w)
        stack.append(i)

      return ans

    for row in matrix:
      for i, num in enumerate(row):
        hist[i] = 0 if num == '0' else hist[i] + 1
      ans = max(ans, largestRectangleArea(hist))

    return ans
 # code by PROGIEZ