# Maximal Rectangle

This page explains Java solution to problem `Maximal Rectangle` using `Stack` data structure.

## Problem Statement

Given a 2D binary matrix filled with `0's` and `1's`, find the largest rectangle containing only `1's` and return its area.

Example 1:

Input:
Input: [
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

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

int m = matrix.length;
int n = matrix[0].length;

int[] row = new int[n];
int maxLength = 0;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(matrix[i][j] == '1') row[j] += 1;
else row[j] = 0;
}
maxLength = Math.max(maxLength, maxRectangle(row));
}
return maxLength;
}

private int maxRectangle(int[] heights) {
Stack<Integer> st = new Stack<>();
st.push(-1);
int maxLength = 0;
for(int i = 0; i < heights.length; i++) {
while(st.peek() != -1 && heights[st.peek()] > heights[i]) {
maxLength = Math.max(maxLength, heights[st.pop()] * (i - st.peek() - 1));
}
st.push(i);
}
while(st.peek() != -1) {
maxLength = Math.max(maxLength, heights[st.pop()] * (heights.length - st.peek() - 1));
}
return maxLength;
}
}
``````

## Time Complexity

O(M * N) Where
M is total number of Rows in an input array
N is total number of Cols in an input array

## Space Complexity

O(N) Where
N is total number of Cols in an input array