Largest rectangle of 1's in 2d binary matrix

user_1042926 0
Viewed 20180

There is a problem to find the maximum area of the 1 in the 0-1 matrix. In this problem there are two cases:

  1. area to be measure is of shape square. that's simple one by DP.

  2. area to be measure is of the shape of rectangle. i am not able to think a optimal solution for this.

Example:

010101
101001
111101
110101

The largest rectangle has an area of 4 (3rd row , 5th column and one more in 3rd,4th row). Can we also get all those rectangle ?

arrays algorithm
6 Answers

Another simpler approach is to use two temp M x N arrays to compute the length of rectangles (row and column wise) - ie count of consecutive 1's then. Traverse the two temp matrices to find max repeating lengths (row and column wise).

Here is the code for the same.

int GetMaxRectangularArea(vector<vector<int>> & matrix, int nRows, int nCols)
{
    vector<vector<int>>  rowLengths(nRows, vector<int>(nCols));
    vector<vector<int>>  colLengths(nRows, vector<int>(nCols));

    // initialize first column of rowLengths with first column of matrix
    for (int i = 0; i < nRows; i++) {
        rowLengths[i][0] = matrix[i][0];
    }

    // initialize first row of colLengths with first row of matrix
    for (int j = 0; j < nCols; j++) {
        colLengths[0][j] = matrix[0][j];
    }

    // Compute row wise length of consecutive 1's in rowLengths
    for (int i = 0; i < nRows; i++) {
        for (int j = 1; j < nCols; j++) {
            if (matrix[i][j] == 1) {
                rowLengths[i][j] = 1 + rowLengths[i][j - 1];
            }
            else {
                rowLengths[i][j] = 0;
            }
        }
    }

    // Compute column wise length of consecutive 1's in colLengths
    for (int j = 0; j < nCols; j++) {
        for (int i = 1; i < nRows; i++) {
            if (matrix[i][j] == 1) {
                colLengths[i][j] = 1 + colLengths[i- 1][j];
            }
            else {
                colLengths[i][j] = 0;
            }
        }
    }

    // Now traverse the rowLengths array to find max length sub array
    int maxArea = 0;

    for (int j = nCols - 1; j >= 0; j--) {
        int currentArea = 0;
        int currentMax = -1;
        int repeats = 1;

        for (int i = nRows - 1; i >= 0; i--) {
            if (rowLengths[i][j] != currentMax) {
                if (currentMax != -1) {
                    currentArea = currentMax * repeats;

                    if (currentArea > maxArea) {
                        maxArea = currentArea;
                    }
                }

                currentMax = rowLengths[i][j];
                repeats = 1;
            }
            else {
                repeats++;
            }
        }

        currentArea = currentMax * repeats;

        if (currentArea > maxArea) {
            maxArea = currentArea;
        }
    }

    for (int i = nRows - 1; i >= 0; i--) {
        int currentArea = 0;
        int currentMax = -1;
        int repeats = 1;

        for (int j = nCols - 1; j >= 0; j--) {
            if (colLengths[i][j] != currentMax) {
                if (currentMax != -1) {
                    currentArea = currentMax * repeats;

                    if (currentArea > maxArea) {
                        maxArea = currentArea;
                    }
                }

                currentMax = colLengths[i][j];
                repeats = 1;
            }
            else {
                repeats++;
            }
        }

        currentArea = currentMax * repeats;

        if (currentArea > maxArea) {
            maxArea = currentArea;
        }
    }

    return maxArea;
}
user_5347330
Related