easyGreedyPure DSA~18 min
Release Hop Reachable
A migration tool upgrades through release versions 0..n-1. From version i it can hop forward up to hops[i] versions in one migration step. Starting at version 0, decide whether it can reach the final version n-1.
Problem
Given an array hops where hops[i] is the maximum forward jump from index i, return true if you can reach the last index starting from index 0.
Input
An array hops of length n (1 ≤ n ≤ 10^5), each value in [0, 10^5].
Output
A boolean — true if the last index is reachable.
Constraints
- 1 ≤ n ≤ 100,000
- 0 ≤ hops[i] ≤ 100,000
- Start at index 0; target is index n - 1
Examples
Example 1
Input
hops = [2, 3, 1, 1, 4]
Output
true
From 0 jump to 1, from 1 jump 3 to reach index 4. Reachable.
Example 2
Input
hops = [3, 2, 1, 0, 4]
Output
false
Every path lands on index 3 whose hop is 0, stranding before index 4.