Find largest sub-matrix with all 1s (not necessarily square)

In last post, we saw a dynamic programming approach to for finding maximum size square sub-matrix with all 1s. In this post, we will discuss how to find largest all 1s sub-matrix in a binary matrix. The resultant sub-matrix is not necessarily a square sub-matrix.

Example:

1  1  0  0  1  0

0  1  1  1  1  1

1  1  1  1  1  0

0  0  1  1  0  0

Largest all 1s sub-matrix is from (1,1) to (2,4).

1  1  1  1

1  1  1  1

Algorithm: If we draw a histogram of all 1’s cells in above rows (until we find a 0) for a particular row, then maximum all 1s sub-matrix ending in that row will the equal to maximum area rectangle in that histogram. Below is the example for 3rd row in above discussed matrix:

If we calculate this area for all the rows, maximum area will be our answer. We can extend our solution very easily to find start and end co-ordinates.

For above purpose, we need to generate an auxiliary matrix S[][] where each element represents the number of 1s above and including it, up until the first 0. S[][] for above matrix will be as shown below:

1  1  0  0  1  0

0  2  1  1  2  1

1  3  2  2  3  0

0  0  3  3  0  0

Now we can simple call our maximum rectangle in histogram on every row in S[][] and update the maximum area every time.

Also we don’t need any extra space for saving S. We can update original matrix (A) to S and after calculation, we can convert S back to A.

Code: I am not writing the code for largestArea() function. One can find its definition in this post.

#define ROW 10  
    #define COL 10  
      
    int find_max_matrix(int A[ROW][COL])  
    {  
     int i, j;  
     int max, cur_max;  
     cur_max = 0;  
      
     //Calculate Auxilary matrix  
     for (i=1; i<ROW; i++)  
         for(j=0; j<COL; j++)  
         {  
             if(A[i][j] == 1)  
                 A[i][j] = A[i-1][j] + 1;  
         }  
      
     //Calculate maximum area in S for each row  
     for (i=0; i<ROW; i++)  
     {       
         max = largestArea(A[i], COL);  
         if (max > cur_max)  
             cur_max = max;  
     }  
      
     //Regenerate Oriignal matrix  
     for (i=ROW-1; i>0; i--)  
         for(j=0; j<COL; j++)  
         {  
             if(A[i][j])  
                 A[i][j] = A[i][j] - A[i-1][j];  
         }  
      
     return cur_max;  
    }  

Complexity: Lets say that total number of rows and columns in A are m and n respectively and N = m*n

Complexity of calculating S = O(m*n) = O(N)

Complexity of LargestArea() for every row = O(n) since there are n elements in every row. Since we called LargestArea() m times so total complexity of calculating largest area = O(m*n) = O(N)

Complexity of converting S to A = O(m*n) = O(N)

So total time complexity = O(N)

Since we are not using any extra space, so space complexity is O(1).

Note: Above function only returns largest area, which can be very easily modified to get start and row indexes as well.