finding max rectangle of 1s

Question

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

Please follow the posting guidelines give in the help documentation. [MCVE](http://stackoverflow.com/help/mcve) applies here. Show the input where your program doesn't work; show the output you got (especially with debugging print statements added). Your problem description is okay. Most of all, you should not ask us whether your program works. You should know this before you post. If you're not sure, *test* it. When you find a problem, we're the place to help you fix it. — Prune, Oct 25 '15 at 06:00
Possible duplicate of [Puzzle: Find largest rectangle (maximal rectangle problem)](http://stackoverflow.com/questions/7245/puzzle-find-largest-rectangle-maximal-rectangle-problem) — m69's been on strike for years, Oct 28 '15 at 03:27

6324 · Accepted Answer · 2017-07-03T18:05:06.440

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

Thanks Ealon, for "length[i - 1][j], length[i][j - 1])" I am not sure if it is correct, since how do you know length[i - 1][j] and length[i][j - 1] could form consecutive square? They just indicate max square using i-1/j or using i/j-1 characters (ending one may not be neighbor [i][j])? Please feel free to correct me if I am wrong. — Lin Ma, Oct 25 '15 at 20:11
I use Math.min(length[i-1][j], length[i][j-1], length[i-1][j-1]) to find which neighbor of length[i][j] can form a square of 1s together with matrix[i][j], . You can write a main function and test my code with inputs. — 6324, Oct 26 '15 at 03:51
Thanks Ealon, love your implementation and mark your reply as answered. Have a good day. :) — Lin Ma, Oct 27 '15 at 20:55

finding max rectangle of 1s

1 Answers1