Harbor Relay Coverage Radius

Published at05 Jan 2026

Like30

You have checkpoint positions along a pier and relay positions that can broadcast in both directions. Every relay uses the same radius, and you want the smallest radius that still covers every checkpoint.

A checkpoint is covered if at least one relay is close enough. That means the radius must be at least the distance from that checkpoint to its nearest relay. The final answer is the largest of those nearest distances.

For example, if checkpoints = [1,5,9] and relays = [2,8], the answer is 3. Checkpoint 1 is 1 unit from relay 2, checkpoint 5 is 3 units from the nearest relay, and checkpoint 9 is 1 unit from relay 8. The biggest gap is 3, so a radius of 3 is enough. If relays = [] while checkpoints still exist, the answer is -1 because nothing can cover them.

So the task is to find the nearest relay for each checkpoint, then return the largest distance you had to use.

Example Input & Output

Example 1

Input

checkpoints = [1,5,9], relays = [2,8]

Output

Explanation

A radius of 3 covers each checkpoint (1 is within 1 of relay 2, 5 within 3 of 2 or 8, and 9 within 1 of 8).

Example 2

Input

checkpoints = [2], relays = []

Output

-1

Explanation

Without relays, no radius provides coverage.

Example 3

Input

checkpoints = [0,10], relays = [4]

Output

Explanation

A radius of 6 reaches both ends from relay position 4.

Algorithm Flow

Recommendation Algorithm Flow for Harbor Relay Coverage Radius

Solution Approach

A nice way to solve this is to look at each checkpoint and find its nearest relay. Since the relay positions are sorted, we can use binary search to find where the checkpoint would be inserted.

If that insertion position is idx, then only two relays can possibly be the nearest ones: relays[idx] on the right, and relays[idx - 1] on the left.

const leftDist = idx > 0 ? Math.abs(checkpoint - relays[idx - 1]) : Infinity;
const rightDist = idx < relays.length ? Math.abs(relays[idx] - checkpoint) : Infinity;
const needed = Math.min(leftDist, rightDist);

The value needed is the smallest radius that covers that single checkpoint. Repeat that for every checkpoint, and keep the maximum needed value. That maximum is the minimum radius that covers them all.

If there are checkpoints but no relays, return -1 immediately. Otherwise, this solution runs in O(n log m) time for n checkpoints and m relays.

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class Solution {
    public int calculate_radius(int[] stations, int[] targets) {
        Arrays.sort(stations);
        int maxR = 0;
        for (int t : targets) {
            int idx = Arrays.binarySearch(stations, t);
            if (idx < 0) {
                idx = -(idx + 1);
                int d1 = (idx > 0) ? t - stations[idx-1] : Integer.MAX_VALUE;
                int d2 = (idx < stations.length) ? stations[idx] - t : Integer.MAX_VALUE;
                maxR = Math.max(maxR, Math.min(d1, d2));
            }
        }
        return maxR;
    }
}

javascript

function calculate_radius(stations, targets) {
    stations.sort((a, b) => a - b);
    let maxR = 0;
    for (let t of targets) {
        let low = 0, high = stations.length - 1;
        let minDist = Infinity;
        while (low <= high) {
            let mid = Math.floor((low + high) / 2);
            minDist = Math.min(minDist, Math.abs(stations[mid] - t));
            if (stations[mid] < t) low = mid + 1;
            else if (stations[mid] > t) high = mid - 1;
            else break;
        }
        maxR = Math.max(maxR, minDist);
    }
    return maxR;
}

php

function calculate_radius($stations, $targets) {
    sort($stations);
    $maxR = 0;
    foreach ($targets as $t) {
        $low = 0; $high = count($stations) - 1;
        $minDist = INF;
        while ($low <= $high) {
            $mid = floor(($low + $high) / 2);
            $minDist = min($minDist, abs($stations[$mid] - $t));
            if ($stations[$mid] < $t) $low = $mid + 1;
            else if ($stations[$mid] > $t) $high = $mid - 1;
            else break;
        }
        $maxR = max($maxR, $minDist);
    }
    return $maxR;
}

python

import bisect
def calculate_radius(stations, targets):
    stations.sort()
    max_r = 0
    for t in targets:
        idx = bisect.bisect_left(stations, t)
        d1 = t - stations[idx-1] if idx > 0 else float('inf')
        d2 = stations[idx] - t if idx < len(stations) else float('inf')
        max_r = max(max_r, min(d1, d2))
    return max_r

rust

pub fn calculate_radius(stations: Vec<i32>, targets: Vec<i32>) -> i32 {
    let mut stations = stations;
    stations.sort();
    let mut max_r = 0;
    for t in targets {
        let res = stations.binary_search(&t);
        match res {
            Ok(_) => {},
            Err(idx) => {
                let d1 = if idx > 0 { t - stations[idx-1] } else { i32::MAX };
                let d2 = if idx < stations.len() { stations[idx] - t } else { i32::MAX };
                max_r = std::cmp::max(max_r, std::cmp::min(d1, d2));
            }
        }
    }
    max_r
}

typescript

function calculate_radius(stations: number[], targets: number[]): number {
    stations.sort((a, b) => a - b);
    let maxR = 0;
    for (let t of targets) {
        let low = 0, high = stations.length - 1;
        let minDist = Infinity;
        while (low <= high) {
            let mid = Math.floor((low + high) / 2);
            minDist = Math.min(minDist, Math.abs(stations[mid] - t));
            if (stations[mid] < t) low = mid + 1;
            else if (stations[mid] > t) high = mid - 1;
            else break;
        }
        maxR = Math.max(maxR, minDist);
    }
    return maxR;
}

Related Binary Search Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Harbor Relay Coverage Radius

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Binary Search Challenges

Marina Beacon Frequency Search

Minimal Climb Cost

Balanced Mod Subarrays

Longest Mod3 Balanced Subarray

Minimize Maximum Distance Between Gas Stations

Find Target Range

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.