LeetCode Problem : Jump Game

LeetCode Problem : Jump Game

Problem Statement

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Overview

Dynamic Programming can be used by iterating over array and check if the current index is reachable. However even with dynamic programming, it's still O(N^2). How to optimize this to O(N) where we only pass an array once : Greedy

Intuition

An index is reachable if you can jump from some of previous reachable index.

Approach

Construct boolean array reachable. Iterate over nums. for each index i check if ith index is reachable from any of reachable indices. We do this by checking all indices that marked as reachable from previous iteration. if reachable, set reachable[i] to true. Keep going upto last index and if last index of reachable true, return true, false otherwise.

Can we do better?

Think of you standing at the position and see which position is the furthest position you can jump to. Keep tracking of this information and do this at each position and at any index if the current index is bigger than position that you can jump furthest, return false. otherwise return true.

Code

//Dynamic Programming : O(N^2)
func canJump(nums []int) bool {
  //declare slice    
  reachable := make([]bool, len(nums))
  reachable[0] = true
  for i:=1; i< len(nums); i++ {
    for j := 0; j < i; j++ {
      if reachable[j] {
        if j+nums[j] >= i {
          reahcable[i] = true
          break
        }
      }
    }
  }
  return myslice[len(nums)-1]
}

func canJump(nums []int) bool {
    furthest:=0
    if len(nums)==1{ 
        return true
    }

    for i:=0;i<len(nums);i++{
        if i>furthest{
           return false
        }
        far=max(far, i+nums[i])
    }
    return true
}

Seed for Interview

Greedy : for each index i, if i is greater than furthest return false. Than compute furthest from i.