Feature #5: Maximum Contiguous Area
Explore how to identify the maximum contiguous area of high cellular network coverage within a rectangular grid. Learn to use recursion and track visited cells to accurately calculate connected regions. Understand the approach to efficiently analyze network signal distribution and its time and space complexities.
We'll cover the following...
Description
In a busy city center, our cellular operator surveyed a mall, which was rectangular in shape. They identified locations within the mall where cellular network signals were satisfactorily high. The result of the study was stored in the form of a rectangular grid of 0s and 1s. Each cell in the matrix is found to correspond to a unit area in the mall. If the value in a cell of this matrix is 1, then this means that the corresponding location in the mall has satisfactory network coverage.
Given an m x n rectangular grid, representing the network coverage in the unit areas, we want to determine the maximum contiguous area with satisfactory coverage.
The maximum contiguous area corresponds to the 4 directionally adjacent (horizontal and vertical) cells with high network coverage, that is, the cells with the value 1 in them.
Let’s review a few examples:
Solution
We want to know the area of each connected shape in the grid, and then take the maximum of these.
Suppose we land on a cell, (r, c), where r represents the row, and c represents the column. In that case, we will need to explore every cell connected to it 4-directionally and recursively all ...