Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Max Leaps in Jump Game (Main Thread)

Here is the interview question prompt, presented for reference.

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).

arr = [1, 3, 2, 2, 1]
idx    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)

You can see the full challenge with visuals at this link.

Challenges • Asked over 6 years ago by Jake from AlgoDaily

Jake from AlgoDaily Commented on Nov 30, 2017:

This is the main discussion thread generated for Max Leaps in Jump Game.

James20999 Commented on Aug 17, 2022:

In the jump game,max leapfrogs as high as possible. When he gets to the top of the jump, he does a flip and lands on his back with his arms outstretched. The essay-on-time is the place where you can learn how you can do this.

tintamaay Commented on Dec 02, 2022:

Children shouldn't waste their time on boring textbooks and classes when they may be focusing on something more beneficial. Today's educational market is papertyper.net reviews Thankfully, there are several businesses that offer cheap writing services to college students

tintamaay Commented on Dec 02, 2022:

https://essaysservicesreviews.com/papertyper-net-review