Relay Towers Down the Valley
A mountain valley has a row of radio relay towers, numbered from 0 at the top to the village at the bottom. An alert starts at tower 0 and must reach the last tower. Each tower can forward the alert down the valley, but only so far: tower i can send it to any of the next reach[i] towers.
Some transmitters are weak, and a few are broken (reach[i] = 0), though a broken tower can still receive. Before the storm season, the rescue team wants to know whether an alert from the top can reach the village at all.
Your task
Write canReachLastTower(reach). From tower i, the alert can go to any tower j with i < j ≤ i + reach[i]. Return true if some chain of forwards takes the alert from tower 0 to tower reach.length - 1, and false otherwise.
With a single tower, the alert is already at the last tower, so return true.
canReachLastTower(reach: int[]) → bool
Examples
reach = [3, 0, 2, 0, 1, 0]
true
Tower 0 can reach towers 1, 2 and 3. Tower 2 can reach 3 and 4. Tower 4 reaches 5, the last one. So 0 → 2 → 4 → 5 works. Towers 1 and 3 are broken, but you do not have to use them.
reach = [2, 1, 0, 3, 1]
false
From tower 0 the alert reaches 1 or 2. Tower 1 reaches only 2. Tower 2 is broken. Nothing ever gets past tower 2, so the strong tower 3 never hears the alert.
Constraints
- 1 ≤ reach.length ≤ 10,000
- 0 ≤ reach[i] ≤ 100,000
Start with brute force
Explore every chain: from tower 0 try every tower it can reach, then every tower those can reach, and so on, with a search that marks visited towers. Without marking, the number of chains grows exponentially. With marking it is correct, but each tower may look at up to reach[i] others, so it is O(n²) in the worst case: about 50 million steps for 10,000 strong towers.
The search tracks which towers are reachable, one by one. You only need to know how far the reachable block extends.
Hints
0 of 4 shown- Hint 1
In the second example, list every tower the alert can possibly reach. Do those towers form a gap-free block starting at 0?
- Hint 2
If the alert can reach tower 5, it can also reach towers 1 to 4: any forward that lands beyond them passed over them from somewhere at or before them. So the reachable towers are always a block 0 to
far. - Hint 3
Walk the towers from left to right, keeping
far, the farthest tower reachable so far. What does it mean if you arrive at a toweriwithi > far? - Hint 4
Set
far = 0. For each toweriin order: ifi > far, the alert can never get here, so return false. Otherwise updatefar = max(far, i + reach[i]). If you finish the loop, return true.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The reachable towers always form one block, starting at tower 0. So instead of tracking a set of towers, track one number: far, the end of that block. Each tower inside the block can push far further.
Trace [2, 1, 0, 3, 1]:
- Tower 0: inside the block (0 ≤ 0).
far = max(0, 0 + 2) = 2. - Tower 1: inside (1 ≤ 2).
far = max(2, 1 + 1) = 2. - Tower 2: inside (2 ≤ 2).
far = max(2, 2 + 0) = 2. - Tower 3: 3 > 2. The alert can never get here, so return
false.
A common wrong idea is to always forward to the farthest tower. In [2, 3, 0, 0, 1, 0] that sends the alert from 0 to the broken tower 2 and gets stuck, while 0 → 1 → 4 → 5 works. Tracking far avoids choosing a route at all.
function canReachLastTower(reach) {
let far = 0; // towers 0..far can all receive the alert
for (let i = 0; i < reach.length; i++) {
if (i > far) return false; // a gap the alert cannot cross
far = Math.max(far, i + reach[i]);
}
return true;
}def can_reach_last_tower(reach):
far = 0 # towers 0..far can all receive the alert
for i, r in enumerate(reach):
if i > far:
return False # a gap the alert cannot cross
far = max(far, i + r)
return TrueRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.