Hoppable
Given an integer list nums
where each number represents the maximum number of hops you can make, determine whether you can reach to the last index starting at index 0
.
Constraints
n ≤ 100,000
wheren
is the length ofnums
.
https://binarysearch.com/problems/Hoppable
ExamplesPermalink
Example 1Permalink
Input
- nums =
[1, 1, 0, 1]
Output
- answer =
False
Explanation
We can’t go past index 2
of the array.
Example 2Permalink
Input
- nums =
[2, 4, 0, 1, 0]
Output
- answer =
True
Explanation
We can jump from index 0
to 1
, and then jump to the end.
Example 3Permalink
Input
- nums =
[1, 0, 0, 0]
Output
- answer =
False
SolutionPermalink
bool solve(vector<int> &nums) | |
{ | |
// go from right to left, determine if each position | |
// can reach last position, if yes, it is sufficient to just | |
// be able to reach this position | |
int size = nums.size(); | |
if (size == 1) | |
{ | |
return true; | |
} | |
else if (nums[0] == 0) | |
{ | |
return false; | |
} | |
int lastReachable = size - 1; | |
for (int i = lastReachable - 1; i >= 0; i--) | |
{ | |
if (i + nums[i] >= lastReachable) | |
{ | |
// it is enough to just reach at this index | |
lastReachable = i; | |
} | |
} | |
return lastReachable == 0; | |
} |
Leave a comment