CODEWITHSUNDEEP
pythonalgorithm
Lin Ma
Lin Ma

Reputation: 10139

finding max rectangle of 1s

I am debugging on the following problem and posted problem statement and code. My question is, I think for loop (for i in range(m) and for j in xrange(n)) is not correct, since it only consider rectangles from the top row? Please feel free to correct me if I am wrong. Thanks.

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

def maximalRectangle(self, matrix):
    if not matrix:
        return 0
    m, n, A = len(matrix), len(matrix[0]), 0
    height = [0 for _ in range(n)]
    for i in range(m):
        for j in xrange(n):
            height[j] = height[j]+1 if matrix[i][j]=="1" else 0
        A = max(A, self.largestRectangleArea(height))
    return A


def largestRectangleArea(self, height):
    height.append(0)
    stack, A = [0], 0
    for i in range(1, len(height)):
        while stack and height[stack[-1]] > height[i]: 
            h = height[stack.pop()]
            w = i if not stack else i-stack[-1]-1 
            A = max(A, w*h)
        stack.append(i)
    return A

Upvotes: 4

Views: 1061

Answers (1)

Ealon
Ealon

Reputation: 4898

My solution in Java:

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

        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] length = new int[rows][cols];
        int result = 0;

        for (int i = 0; i < rows; i++) {
            length[i][0] = Character.getNumericValue(matrix[i][0]);
            result = Math.max(result, length[i][0]);
        }

        for (int j = 0; j < cols; j++) {
            length[0][j] = Character.getNumericValue(matrix[0][j]);
            result = Math.max(result, length[0][j]);
        }

        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    length[i][j] = Math.min(
                            Math.min(length[i - 1][j], length[i][j - 1]),
                            length[i - 1][j - 1]) + 1;
                    result = Math.max(result, length[i][j] * length[i][j]);
                }
            }
        }

        return result;
    }
}

Upvotes: 4

Related Questions