Feature #1: Determine Location
Explore how to determine the furthest location within a rectangular signal loss matrix where a handset remains usable. This lesson teaches you to apply a binary search approach starting from the bottom-left corner to efficiently identify the maximum range under a given loss threshold. Gain skills in analyzing 2D arrays, leveraging matrix properties for optimization, and understanding time and space complexity for real-world cellular network 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 we move towards the right of the region. The signal loss also increases as we 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 ...