# Speeding up solution to algorithm

Working on the following algorithm:

Given an array of non-negative integers, you are initially positioned

at the first index of the array.Each element in the array represents your maximum jump length at that

position.Determine if you are able to reach the last index.

For example:

`A = [2,3,1,1,4]`

, return`true`

.`A = [3,2,1,0,4]`

, return`false`

.

Below is my solution. It tries every single potential step, and then memoizes accordingly. So if the first element is three, the code takes three steps, two steps, and one step, and launches three separate functions from there. I then memoized with a hash. My issue is that the code works perfectly fine, but it’s timing out for very large inputs. Memoizing helped, but only a little bit. Am I memoizing correctly or is backtracking the wrong approach here?

```
def can_jump(nums)
@memo = {}
avail?(nums, 0)
end
def avail?(nums, index)
return true if nums.nil? || nums.empty? || nums.length == 1 || index >= nums.length - 1
current = nums[index]
true_count = 0
until current == 0 #try every jump from the val to 1
@memo[index + current] ||= avail?(nums, index + current)
true_count +=1 if @memo[index + current] == true
current -= 1
end
true_count > 0
end
```

### 2 Solutions collect form web for “Speeding up solution to algorithm”

Here’s a *?*(?) algorithm:

- Initialize ??? to 0.
- For each number ?
_{?}in ?:- If ? is greater than ???, neither ?
_{?}nor any subsequent number can be reached, so- return
**false**.

- return
- If ?
_{?}+? is greater than ???, set ??? to ?_{?}+?.

- If ? is greater than ???, neither ?
- If ??? is greater than or equal to the last index in ?
- return
**true**. - Otherwise return
**false**.

- return

Here’s a Ruby implementation:

```
def can_jump(nums)
max_reach = 0
nums.each_with_index do |num, idx|
return false if idx > max_reach
max_reach = [idx+num, max_reach].max
end
max_reach >= nums.size - 1
end
p can_jump([2,3,1,1,4]) # => true
p can_jump([3,2,1,0,4]) # => false
```

See it on repl.it: https://repl.it/FvlV/1

Your code is O(n^2), but you can produce the result in O(n) time and O(1) space. The idea is to work backwards through the array keeping the minimum index found so far from which you can reach index n-1.

Something like this:

```
def can_jump(nums)
min_index = nums.length - 1
for i in (nums.length - 2).downto(0)
if nums[i] + i >= min_index
min_index = i
end
end
min_index == 0
end
print can_jump([2, 3, 1, 1, 4]), "\n"
print can_jump([3, 2, 1, 0, 4]), "\n"
```