Good evening! Here's our prompt for today.

We have an array that model square blocks on a city street. On each block is a non-negative whole number.

Ever heard of hopscotch? Picture that as an array:

[1, 3, 2, 2, 1]

Now, in hopscotch, you need to jump in patterns from the start to the end of the boxes. We can model that behavior in the above array-- so we begin at the first index and see the number 1.

Let also assume that each integer in the array represents a maximum jump length from that index. So at index 0, we encounter the value 1, and thus can jump 1 time to the next block. This lets us make our way over to index 1 (which contains 3).

1arr = [1, 3, 2, 2, 1]
2idx    0, 1, 2, 3, 4

However, with numbers greater than 1, we don't always have to take the maximum leap. At index 1, since the max jump is 3, we can choose to jump either 1, 2, or 3 squares (but no more than that).

Example 1

Following this logic, can you write an algorithm that determines if we are able to make it until the very end? In our example of [1, 3, 2, 2, 1], we can make the following moves:

1. 1 leap from index 0 to 1
2. 3 leaps that get us from index 1 to 4

Since we can get to index 4, we would return true.

Example 2

On the other hand, here's an example that wouldn't work:

[2, 1, 0, 1, 4]

Regardless of whether we jump once or twice at the first element, we have to end up at index 2. Then, because the max jump at index 2 is 0, we can never progress beyond that, and thus would return false.

Constraints

• Length of the array <= 100000
• The values of the array will be between 0 and 1000000000
• Expected time complexity : O(n)
• Expected space complexity : O(1)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

var assert = require('assert');

​

/**

 * @param {number[]} nums

 * @return {boolean}

 */

function maxLeaps(nums) {

  // figure this out

  return nums;

}

​

try {

  assert.equal(maxLeaps([1, 3, 2, 2, 1]), true);

​

  console.log('PASSED: ' + '`maxLeaps([1, 3, 2, 2, 1])` should return `true`');

} catch (err) {

  console.log(err);

}

​

try {

  assert.equal(maxLeaps([2, 1, 0, 1, 4]), false);

​

  console.log('PASSED: ' + '`maxLeaps([2, 1, 0, 1, 4])` should return `false`');

} catch (err) {

  console.log(err);

}

​

Here's a video of us explaining the solution.

To change the speed of the video or see it in full screen, click the icons to the right of the progress bar.

Here's our guided, illustrated walk-through.

How do I use this guide?