Feature #2: Low Coverage Area

Description

In a busy city center, our cellular operator has surveyed a mall, which happens to be rectangular in shape. They have identified locations within the mall where cellular network signals are unacceptably low. The result of the study is stored in the form of a rectangular matrix of 0s and 1s. Each cell in the matrix corresponds to a unit area in the mall. If the value in a cell of this array is 1, it means the corresponding location in the mall does not have good network coverage. The operator is considering deploying small radio sites inside the mall. These sites use beamforming technology, which enables providing coverage to a rectangular region. We need to determine the rectangle with the largest area with unacceptable coverage throughout.

We’ll be provided with an m x n matrix of 0s and 1s. We have to find the area of the largest rectangle containing only 1s since that will represent the largest, low coverage, rectangular part of the mall.

Solution

We will attempt to solve the smallest portion of the input in the original problem and gradually build to larger chunks of the input until we find the answer to the problem using the original input. To this end, we will first determine the area of the largest rectangle of 1s considering only the first row of the input. Then, we will find the area of the largest rectangle ending at the second row of input and including the first one. We will repeat this process on increasing subproblem sizes. As we keep increasing the subproblem size while maintaining the maximum area, we will find the area of the largest group of contiguous 1s in the original input.

To determine the maximum area rectangle within a subset of consecutive rows from the input, we will maintain a list, dp, with a size equal to the number of columns in the input matrix. After k iterations of our algorithm, the ith element in the dp list will hold the number of consecutive 1s in column i ending at the kth row of the input. For example, when we process the first row of the input shown above, [0 1 1], we want the list dp to hold [0 1 1]. How do we determine the maximum area of consecutive 1s in this list, meaning just the first row of the original input? We can again apply the divide and conquer strategy and look at a gradually increasing number of columns from the dp list.

As we process one column from dp, we determine the maximum area of consecutive 1s that that column is part of. For instance, if we consider the first column of dp, what’s the largest area of consecutive 1s? Since dp is [0 1 1], the answer is 0 because the first column has no 1s. How about the second column? If it were part of a rectangle of 1s, it would span the second and third column - with a width of 2, height of 1, and with an area(height * width) of 2. The same goes for the third column of dp as well. The maximum area we’ve seen so far is ...