Largest Rectangle in Histogram, Maximal Square, Maximal Rectangle

Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example,
Given height = [2,1,5,6,2,3],
return 10.

Brute Force Solution

• for each height, go back and find the largest area. O(n^2)

public int largestRectangleArea(int[] height) {
    int n= height.length, maxarea=0;
    for(int i=0;i<n;i++){
        int currentmin = height[i];
        for(int j=i;j>=0;j--){
            currentmin = Math.min(height[j], currentmin);
            maxarea = Math.max(maxarea, (i-j+1)*currentmin);
        }
    }
    return maxarea;
}

Solution

• Skip when current height is not peek

public int largestRectangleArea(int[] height) {
    int n= height.length, maxarea=0;
    for(int i=0;i<n;i++){
        int currentmin = height[i];
        if((i+1) < n && height[i] <= height[i+1]){//skip
            continue;
        }
        for(int j=i;j>=0;j--){
            currentmin = Math.min(height[j], currentmin);
            maxarea = Math.max(maxarea, (i-j+1)*currentmin);
        }
    }
    return maxarea;
}

O(n) Solution

public int largestRectangleArea(int[] height) {
    Stack<Integer> stk = new Stack<Integer>();
    int i=0, maxarea=0;
    while(i<height.length){//push when increasing
        if(stk.isEmpty() || height[i]>=height[stk.peek()]){
            stk.push(i);
            i++;
        }
        else{//keep updating when stk.pop is bigger than current
            int pre = stk.pop();
            int h = height[pre];
            int w = stk.isEmpty() ? i : (i-stk.peek()-1);
            maxarea = Math.max(maxarea, w * h);
        }
    }
    while(!stk.isEmpty()){//pop the rest
        int pre = stk.pop();
        int h = height[pre];
        int w = stk.isEmpty() ? i : (i-stk.peek()-1);
        maxarea = Math.max(maxarea, w * h);
    }
    
    return maxarea;
}

---

Maximal Square

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing all 1’s and return its area.
For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.

DP Solution

• max square length with i,j as right-bottom corner
• when current cell is 1, dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i-1][j-1]), dp[i][j-1]) + 1;

public int maximalSquare(char[][] matrix) {
        if(matrix==null || matrix.length == 0) return 0;
        int maxside=0;
        int[][] dp = new int[matrix.length][matrix[0].length]; //max square length with i,j as right-bottom corner
        //init
        for(int i=0; i<matrix[0].length; i++){
            dp[0][i] = matrix[0][i] - '0';
            maxside = Math.max(maxside, dp[0][i]);
        }
        for(int i=0; i<matrix.length; i++){
            dp[i][0] = matrix[i][0] - '0';
            maxside = Math.max(maxside, dp[i][0]);
        }
        //fill
        for(int i=1; i<matrix.length; i++){
            for(int j=1; j<matrix[0].length;j++){
                if((matrix[i][j] - '0') == 1){
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i-1][j-1]), dp[i][j-1]) + 1;
                    maxside = Math.max(maxside, dp[i][j]);
                }
            }
        }
        return maxside * maxside;
    }

---

Maximal Rectangle

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

Solution

• view each row as a accumulated histogram, keep updating the max rectangle row by row

public static int maximalRectangle(char[][] m) {
		if(m==null || m.length==0) return 0;
		int[] bar = new int[m[0].length+1];
		int maxarea=0;
		//increment histogram
		for(int i=0;i<m.length;i++){//for each row
			Stack<Integer> stk = new Stack<Integer>();
			for(int j=0;j<(m[0].length+1);j++){//cols
				if(j<m[0].length){
					if(m[i][j] - '0' == 1){
						bar[j]+=1;
					}
					else bar[j]=0;
				}
				//check if increasing
				if(stk.isEmpty() || bar[j]>=bar[stk.peek()]){
					stk.push(j);
				}
				else{
					while(!stk.isEmpty() && bar[j]<bar[stk.peek()]){
						int pre = stk.pop();
						int h = bar[pre];
						int w = stk.isEmpty() ? j : (j-1-stk.peek());
						maxarea = Math.max(maxarea, w * h);
					}
					stk.push(j);
				}
			}
		}
		return maxarea;
	}