Feature #1: Determine Location

Description

Using a base station located in the top left corner, a cellular operator serves a rectangular region. They have done a road test where they measured the strength of the signal received from their network in a rectangular region. They recorded the loss in signal strength perceived at various parts of the region. The signal loss increases when you move towards the right of the region. The signal loss also increases as you move vertically towards the bottom of the region. To do this, the operator targets a specific handset that works as long as the signal strength does not fall below a certain threshold value. We want to determine the farthest point from the base station within this rectangular region where the handset will work.

We’ll be provided with a 2D matrix consisting of signal strength loss values and a threshold loss value. We need to determine the furthest location beyond which the handset will not work.

Solution

We can take advantage of the fact that the value of our matrix increases as we move right in the row and down the column, and we can perform a kind of binary search on this. We can observe that from a current value, cVal, in a column, all values above it will be smaller. So, if our cVal is already smaller than the target loss value, we know that all values above cVal in the current column will also be smaller than this loss value. Taking this observation into ...