Feature #1: Determine Location
Explore how to determine the furthest location from a base station where a handset remains functional despite signal loss. Learn to analyze a 2D matrix of signal strength losses and apply an efficient search strategy that leverages sorted matrix properties. Understand the solution's time and space complexity as you gain skills applicable to real-world cellular network optimization problems.
We'll cover the following...
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, c_val, in a column, all values above it will be smaller. So, if our c_val is already ...