Skip to Content

Maximum rectangle in a matrix

Home | Coding Interviews | Dynamic Programming | Maximum rectangle in a matrix

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.

class Solution {
  public int maximalRectangle(char[][] matrix) {
    if (matrix.length <= 0) return 0;
    int n = matrix.length;
    int m = matrix[0].length;
    int[][] dp = new int[n][m];
    int maxArea = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (i == 0)
		  dp[i][j] = matrix[i][j] == '1' ? 1 : 0;
        else
		  dp[i][j] = matrix[i][j] == '1' ? (dp[i-1][j] + 1) : 0;
        int min = dp[i][j];
        for (int k = j; k >= 0; k--) {
          if (min == 0) break;
          if (dp[i][k] < min) min = dp[i][k];
          maxArea = Math.max(maxArea, min * (j - k + 1));
        }
      }
    }
    return maxArea;
  }
}

Posted by Jamie Meyer 18 days ago