Leetcode 45 Jump game

leetcode_45_jump_game.rb

Leetcode 45 Jump game

# @param {Integer[]} nums
# @return {Integer}
def jump(nums)
    
    # Explanation:
    # Example: [6,4,3,1,1,5,4,3,2,3,1,9,7,4,3,2,1,1,6,2,1]
    # for each ele in loop
    # for current ele, check the next possible window with ele sized elements
    # current el => 6, next possible window [4,3,1,1,5,4]
    # Now, calculate the weight for each window ele with current ele 
    # I mean (window ele - position index of window)
    # Like, [4-5, 3-4, 1-3, 1-2, 5-1, 4-0] => [-1, -1, -2, -1, 4, 4]
    # now get the any max and jump to that index and update i to that index
    # repeate above until at any point that window for current ele have end index N

    steps = 0
    i = 0
    n = nums.length

    # base case
    return 0 if n <= 1 

    while (i < n) do
        curr_ele = nums[i]
        if i + nums[i] >= n - 1
            # This is the last iteration
            return steps + 1
        end
        window_to_check = nums[i+1..i+nums[i]]
        window_to_check = window_to_check.each_with_index.map {|x,inde| x-(curr_ele - inde + 1)}
        index_to_jump = index_of_first_max(window_to_check)
        i = i + index_to_jump + 1
        steps = steps + 1
    end
    steps
end

def index_of_first_max(array)
  max_value = array.max
  array.each_with_index do |value, index|
    return index if value == max_value
  end
end