Feature #4: Query Peak Users

Description

The cellular operator serves a rectangular region, represented by a 2D grid with one base station in each cell. Each base station is limited in the number of simultaneous users. During busy hours, some users get poor or no service. The company leadership wants to fix this problem by deploying multiple base stations, wherever necessary. Since this is a capital-intensive plan, we want to systematically deploy new base stations only where they are bound to help the most.

The operator has gathered the peak number of users connected to each base station. The executives want to query the obtained data and calculate the peak number of users that are connected to the base stations in a rectangular subset of the covered area. The executives may need to query the data multiple times. Therefore, we need to figure out an efficient way to execute the queries and return their results.

Note: The area to be queried is identified by the top-left and bottom-right cell coordinates.

The following illustration will help clarify to this problem:

Solution

A beginner’s way of solving this problem is to use nested loops to iterate over the rectangular region, represented by the top-left $(row1, col1)$ and bottom-right $(row2, col2)$ coordinates, and sum up all the elements in that region.

Since the executives may want to query the data multiple times, it would make sense for us to perform some pre-processing.

Caching

We could use extra space for speeding up the algorithm by pre-calculating all the possible rectangular regions and storing them in a hash map. This way, all the queries will take constant time. However, the space complexity will blow up, because we have to store all the possible regions.

Let’s see how we can build on this intuition of caching the results.

Caching rows

Imagine pre-computing the cumulative sum of the elements for each row in the grid. We can derive a formula that will calculate the cumulative sum for each individual row $i$, ranging from $0 ...rows - 1$ (inclusive):

$$cache[i][j]=\begin{cases}\sum_{k=0}^{j-1} users[i][k]& j \gt 0 \\ 0 & j = 0\end{cases}$$

Here, $j$ ranges from $0$ to the total number of columns, $(cols)$ in the input grid users. We will calculate the prefix sum of all the cells in a row and store them at the appropriate cell in a 2D grid cache of order $rows \times cols + 1$. We can simplify the notation given above and make use of the sum calculated in the last iteration:

$$cache[i][j+1]=\{\begin{array}{ll}users[i][j]+cache[i][j]& \end{array}$$ ...