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

  • Hash “has_key” complexity in Ruby
  • Time complexity of gsub
  • 2 Solutions collect form web for “Speeding up solution to algorithm”

    Here’s a ?(?) algorithm:

    1. Initialize ??? to 0.
    2. For each number ?? in ?:
      1. If ? is greater than ???, neither ?? nor any subsequent number can be reached, so
        • return false.
      2. If ??+? is greater than ???, set ??? to ??+?.
    3. If ??? is greater than or equal to the last index in ?
      • return true.
      • Otherwise return false.

    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"
    
    Ruby is the best programming language in the world - Ruby on Rails.