Find the area of the largest rectangle of 1’s in a binary matrix
Given a rectangular binary matrix, calculate the area of the largest rectangle of 1's in it. Assume that a rectangle can be formed by swapping any number of columns with each other.
For example,
[0, 1, 0, 1, 1]
[1, 1, 0, 0, 1]
[1, 1, 0, 1, 1]
[1, 1, 1, 1, 1]
Output: The area of the largest rectangle of 1’s is 9
Explanation: The largest rectangle of 1’s can be formed by swapping column 3 with column 5.
[0, 1, 1, 1, 0]
[1, 1, 1, 0, 0]
[1, 1, 1, 1, 0]
[1, 1, 1, 1, 1]
Input:
[0, 1, 1, 0]
[1, 0, 0, 1]
[1, 1, 0, 1]
[1, 1, 1, 1]
Output: The area of the largest rectangle of 1’s is 6
Explanation: The largest rectangle of 1’s can be formed by swapping column 2 with column 4 or swapping column 3 with column 4.
[0, 0, 1, 1]
[1, 1, 0, 0]
[1, 1, 0, 1]
[1, 1, 1, 1]
OR
[0, 1, 0, 1]
[1, 0, 1, 0]
[1, 1, 1, 0]
[1, 1, 1, 1]
1. The idea is to create an auxiliary matrix aux of the same size as the input matrix and fill it with the count of consecutive 1's present in each column of the input matrix. For example, consider the following input matrix:
[0, 1, 0, 1, 1]
[1, 1, 0, 0, 1]
[1, 1, 0, 1, 1]
[1, 1, 1, 1, 1]
Here’s how the auxiliary matrix would look like after this step.
[0, 4, 0, 1, 4]
[3, 3, 0, 0, 3]
[2, 2, 0, 2, 2]
[1, 1, 1, 1, 1]
2. Next, create a count matrix count initialized with 0's and update it using elements of the auxiliary matrix aux as an index, i.e., for each cell (i, j) of the count matrix, do count[i][aux[i][j]] += 1. Here’s how the count matrix would look after this step:
[0, 1, 0, 0, 2]
[0, 0, 0, 3, 0]
[0, 0, 4, 0, 0]
[0, 5, 0, 0, 0]
3. Since the auxiliary matrix contains “count” of consecutive 1's in each column and the count matrix stores information about the total number of times that “count” appeared in each row, the maximum area of each cell (i, j) can be calculated by taking the product of each element aux[i][j] in the auxiliary matrix with its corresponding value count[i][aux[i][j]] in the count matrix. Here’s how the matrix would look like after this step.
[0, 8, 0, 1, 8]
[9, 9, 0, 0, 9]
[8, 8, 0, 8, 8]
[5, 5, 5, 5, 5]
The largest rectangle area of 1's is 9, which would be the largest value in the above matrix.
Following is the implementation of the above algorithm in C, Java, and Python. The solution is highly optimized to save space. For instance, instead of building an auxiliary array, the input matrix is updated with the count of consecutive 1's. Instead of using the count matrix, a count array is used for each row.
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
#include <stdio.h> #include <limits.h> // `M × N` matrix #define M 4 #define N 5 // Utility function to replace all non-zero values in a matrix by 1 void resetMatrix(int mat[][N]) { for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { if (mat[i][j] != 0) { mat[i][j] = 1; } } } } // Utility function to find the maximum of two numbers int max(int x, int y) { return (x > y) ? x : y; } // Function to calculate the area of the largest rectangle of 1's where swapping of // columns is allowed int findMaxRectArea(int mat[][N]) { // update the matrix to store the counts of consecutive 1's present in each column for (int j = 0; j < N; j++) { // process each column from bottom to top for (int i = M - 2; i >= 0; i--) { if (mat[i][j] == 1) { mat[i][j] = mat[i+1][j] + 1; } } } // keep track of the largest rectangle of 1's found so far int maxArea = 0; // traverse each row in the modified matrix to find the maximum area for (int i = 0; i < M; i++) { // create a count array for each row `i` int count[M + 1] = { 0 }; // process row `i` for (int j = 0; j < N; j++) { if (mat[i][j] > 0) { // increment value in the count array using the current element // as an index count[mat[i][j]] += 1; // the area can be calculated by multiplying the current // element `mat[i][j]` with the corresponding value // in the count array `count[mat[i][j]]` maxArea = max(maxArea, mat[i][j] * count[mat[i][j]]); } } } // reset matrix before returning resetMatrix(mat); return maxArea; } int main(void) { int mat[M][N] = { { 0, 1, 0, 1, 1 }, { 1, 1, 0, 0, 1 }, { 1, 1, 0, 1, 1 }, { 1, 1, 1, 1, 1 } }; printf("The area of the largest rectangle of 1's is %d", findMaxRectArea(mat)); return 0; } |
Output:
The area of the largest rectangle of 1’s is 9
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
class Main { // Utility function to replace all non-zero values in a matrix by 1 public static void resetMatrix(int[][] mat) { for (int i = 0; i < mat.length; i++) { for (int j = 0; j < mat[0].length; j++) { if (mat[i][j] != 0) { mat[i][j] = 1; } } } } // Function to calculate the area of the largest rectangle of 1's where // swapping of columns is allowed public static int findMaxRectArea(int[][] mat) { // base case if (mat == null || mat.length == 0) { return 0; } // `M × N` matrix int M = mat.length; int N = mat[0].length; // update the matrix to store the counts of consecutive 1's present // in each column for (int j = 0; j < N; j++) { // process each column from bottom to top for (int i = M - 2; i >= 0; i--) { if (mat[i][j] == 1) { mat[i][j] = mat[i+1][j] + 1; } } } // keep track of the largest rectangle of 1's found so far int maxArea = 0; // traverse each row in the modified matrix to find the maximum area for (int i = 0; i < M; i++) { // create a count array for each row `i` int[] count = new int[M + 1]; // process row `i` for (int j = 0; j < N; j++) { if (mat[i][j] > 0) { // increment value in the count array using the // current element `mat[i][j]` as an index count[mat[i][j]] += 1; // the area can be calculated by multiplying the current // element `mat[i][j]` with the corresponding value // in the count array `count[mat[i][j]]` maxArea = Integer.max(maxArea, mat[i][j] * count[mat[i][j]]); } } } // reset matrix before returning resetMatrix(mat); return maxArea; } public static void main(String[] args) { int[][] mat = { { 0, 1, 0, 1, 1 }, { 1, 1, 0, 0, 1 }, { 1, 1, 0, 1, 1 }, { 1, 1, 1, 1, 1 } }; System.out.println("The area of the largest rectangle of 1's is " + findMaxRectArea(mat)); } } |
Output:
The area of the largest rectangle of 1’s is 9
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
# Utility function to replace all non-zero values in a matrix by 1 def resetMatrix(mat): for i in range(len(mat)): for j in range(len(mat[0])): if mat[i][j] != 0: mat[i][j] = 1 # Function to calculate the area of the largest rectangle of 1's where swapping of # columns is allowed def findMaxRectArea(mat): # base case if not mat or not len(mat): return 0 # `M × N` matrix M = len(mat) N = len(mat[0]) # update the matrix to store the counts of consecutive 1's present in each column for j in range(N): # process each column from bottom to top for i in reversed(range(0, M - 1)): if mat[i][j] == 1: mat[i][j] = mat[i + 1][j] + 1 # keep track of the largest rectangle of 1's found so far maxArea = 0 # traverse each row in the modified matrix to find the maximum area for i in range(M): # create a count array for each row `i` count = [0] * (M + 1) # process row `i` for j in range(N): if mat[i][j] > 0: # increment value in the count array using the current element # as an index count[mat[i][j]] += 1 # the area can be calculated by multiplying the current # element `mat[i][j]` with the corresponding value in the # count array `count[mat[i][j]]` maxArea = max(maxArea, mat[i][j] * count[mat[i][j]]) # reset matrix before returning resetMatrix(mat) return maxArea if __name__ == '__main__': mat = [ [0, 1, 0, 1, 1], [1, 1, 0, 0, 1], [1, 1, 0, 1, 1], [1, 1, 1, 1, 1] ] print("The area of the largest rectangle of 1's is", findMaxRectArea(mat)) |
Output:
The area of the largest rectangle of 1’s is 9
The time complexity of the proposed solution is O(M × N), where M is the total number of rows and N is the total number of columns in the input matrix. The auxiliary space required by the program is O(M).
Calculate the size of the largest plus of 1’s in a binary matrix
Find the size of the largest square submatrix of 1’s present in a binary matrix
Find the index of a row containing the maximum number of 1’s in a binary matrix
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)