1 minute read

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 where n is the length of nums.

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;
}
view raw Hoppable.cpp hosted with ❤ by GitHub

Leave a comment