My java solution based on Maximum Rectangle in Histogram with explanation


  • 78
    O

    We can apply the maximum in histogram in each row of the 2D matrix. What we need is to maintain an int array for each row, which represent for the height of the histogram.

    Please refer to https://leetcode.com/problems/largest-rectangle-in-histogram/ first.

    Suppose there is a 2D matrix like

    1 1 0 1 0 1

    0 1 0 0 1 1

    1 1 1 1 0 1

    1 1 1 1 0 1

    First initiate the height array as 1 1 0 1 0 1, which is just a copy of the first row. Then we can easily calculate the max area is 2.

    Then update the array. We scan the second row, when the matrix[1][i] is 0, set the height[i] to 0; else height[i] += 1, which means the height has increased by 1. So the height array again becomes 0 2 0 0 1 2. The max area now is also 2.

    Apply the same method until we scan the whole matrix. the last height arrays is 2 4 2 2 0 4, so the max area has been found as 2 * 4 = 8.

    Then reason we scan the whole matrix is that the maximum value may appear in any row of the height.

    Code as follows:

    public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        
        int[] height = new int[matrix[0].length];
        for(int i = 0; i < matrix[0].length; i ++){
            if(matrix[0][i] == '1') height[i] = 1;
        }
        int result = largestInLine(height);
        for(int i = 1; i < matrix.length; i ++){
            resetHeight(matrix, height, i);
            result = Math.max(result, largestInLine(height));
        }
        
        return result;
    }
    
    private void resetHeight(char[][] matrix, int[] height, int idx){
        for(int i = 0; i < matrix[0].length; i ++){
            if(matrix[idx][i] == '1') height[i] += 1;
            else height[i] = 0;
        }
    }    
    
    public int largestInLine(int[] height) {
        if(height == null || height.length == 0) return 0;
        int len = height.length;
        Stack<Integer> s = new Stack<Integer>();
        int maxArea = 0;
        for(int i = 0; i <= len; i++){
            int h = (i == len ? 0 : height[i]);
            if(s.isEmpty() || h >= height[s.peek()]){
                s.push(i);
            }else{
                int tp = s.pop();
                maxArea = Math.max(maxArea, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
                i--;
            }
        }
        return maxArea;
    }
    

    }


  • 0
    S

    Good solution. Thanks for sharing.


  • 0
    L

    Thanks for sharing the nice solution. Running time should be NNlog(N), I only thought of the N^3 solution.


  • 1
    N

    I thought the time complexity should be O(2MN), right? For each row, we do N(resetHeight) + N(calculate maxArea), and we repeat this by M (rows) times.

    Btw, this is really excellent solution! Thanks for sharing!


  • 7
    K

    Similar approach in C++. 20ms.

    int maximalRectangle(vector<vector<char>>& matrix) {
      if(matrix.size()==0) return 0;
    
      int ans = 0, m = matrix.size(), n = matrix[0].size();
      vector<int> height(n,0); // 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 = min(pre,height[cur]);
            ans = max(ans, (j-cur+1)*pre);
          }
          ans = max(ans, height[j]);
        }
      }
      return ans;
    }

  • 0
    C

    Great answer! Thanks!


  • 0
    P

    Thanks for sharing this readable solution!


  • 0
    W

    I think the time complexity of your answer is O(n^3), also in practice it runs fast


  • 0
    B

    @wxnfifth I think the time complexity should be O(N^2), O(N^2) for scanning all items in matrix, O(N) for calculate max area in histogram, so it's O(N^2)


  • 0
    B

    @kalaexj cannot believe it, you solution is so concise and neat


  • 0
    O

    @bradshell Yes it is. For each row, scanning takes O(N), generate the histogram takse O(N), calculating the maximum rectangle in this also row takes O(N), which means in total it still takes O(N) for each row. So for the whole 2D matrix, it takes N * O(N) which is O(N^2).


  • 0
    S

    Nice video explanation here: https://www.youtube.com/watch?v=g8bSdXCG-lA


  • 1
    J

    @bu.will.9 said in My java solution based on Maximum Rectangle in Histogram with explanation:

    2 4 2 2 0 2

    The solution is so nice, I l learnt a lot. but just to verify, the last column in height array should be 4 right?

    2 4 2 2 0 4


  • 0
    O

    @surajr Yes it should be 4. My mistake. Correcting it.


  • 0
    S

    Thank you so much for the detailed explanation @ObjectNotFound .
    Though I found the code too long.

    Here is the Java version of @kalaexj 's C++ code which is based on the same concept.

    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;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.