Largest area of rectangle with permutations

Given a binary grid i.e. a 2D grid only consisting of 0’s and 1’s, find the area of the largest rectangle inside the grid such that all the cells inside the chosen rectangle should have 1 in them. You are allowed to permutate the columns matrix i.e. you can arrange each of the column in any order in the final grid. Please follow the below example for more clarity.

Lets say we are given a binary grid of 3 * 3 size.

1 0 1

0 1 0

1 0 0

At present we can see that max rectangle satisfying the criteria mentioned in the problem is of 1 * 1 = 1 area i.e either of the 4 cells which contain 1 in it. Now since we are allowed to permutate the columns of the given matrix, we can take column 1 and column 3 and make them neighbours. One of the possible configuration of the grid can be:

1 1 0

0 0 1

1 0 0

Now In this grid, first column is column 1, second column is column 3 and third column is column 2 from the original given grid. Now, we can see that if we calculate the max area rectangle, we get max area as 1 * 2 = 2 which is bigger than the earlier case. Hence 2 will be the answer in this case.

Method:

Steps -

1. Store the number of contiguous 1s of the columns in another array. This sum actually gives the height of the histogram starting from that column.

For example, for the given matrix -
1 0 1
1 1 0
0 1 0

The required count array will be -

1 0 1
2 1 0
0 2 0

The way to interpret this is that there is a histogram of height 2 based at grid[1][0] and grid[2][1] and so on.

2. Now sort the rows of the count array in decreasing order. This sorting is the swapping of columns which is allowed in this problem.

Note - There is no problem if individual elements of a column end up at different columns. This is because we have already stored the count of contiguous 1s above the current element which is all we need for area calculation.

Sorting gives -

1 1 0
2 1 0
2 0 0

3. Now since the histograms are arranged in decreasing heights, for a given count[i][j] with height H, there will always be a histogram of at least height H before it. This means that the rectangular area under the histograms for count[i][j] will be -

=> base * min_height_till_now_for_current_row

=> (j + 1) * count[i][j]

Here the areas will be -

1 2 0
2 2 0
2 0 0

4. Return the max area from these calculated areas.

Solution:

Time: O(r * (r + c))
Space: O(r * c)

public class Solution {
    public int solve(int[][] A) {
        int r = A.length;
        if (r == 0) return 0;
        int c = A[0].length;
        int[][] hist = new int[r][c];
        // create histogram
        for (int i = 0; i < r; i ++) {
            for (int j = 0; j < c; j ++) {
                if (i == 0) {
                    hist[i][j] = A[i][j];
                } else {
                    hist[i][j] = A[i][j] == 1 ? hist[i - 1][j] + 1 : 0;
                }
            }
        }
        // sort each row of histogram by count sort
        for (int i = 0; i < r; i ++) {
            int[] count = new int[r + 1];
            for (int j = 0; j < c; j ++) {
                count[hist[i][j]] ++;
            }
            int col = 0;
            // runs R + C
            for (int k = r; k >= 0; k --) {
                // runs C times
                while (count[k] > 0) {
                    hist[i][col++] = k;
                    count[k]--;
                }
            }
        }
        // get max area
        int max = 0;
        for (int i = 0; i < r; i ++) {
            for (int j = 0; j < c; j ++) {
                max = Math.max(max, (j + 1) * hist[i][j]);
            }
        }
        // for (int[] arr : hist) System.out.println(Arrays.toString(arr));
        return max;
    }
}