## Question

>[Leetcode.55 Jump Game
](https://leetcode.com/problems/jump-game/description/)

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

- Time complexity: O(N)
- Space complexity: O(1)

:::

<br>

## Thoughts & Solutions

### YC
:::spoiler Code

// Time O(n) | Space O(1) - where n is the length of the array

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    let max = 0;
    for(let i = 0; i <= max; i++){
        max = Math.max(max, i + nums[i]);
        if(max >= nums.length - 1) return true
    }
    return false;
};

:::

<hr/>

### Sol
#### Mark Reachable Indices
Time: O(N^2)
Space: O(N)
:::spoiler Code

var canJump = function(nums) {
    let goal = nums.length-1
    for(i=nums.length-1;i>=0; i--){
        if(i + nums[i]>=goal){
            goal= i
        }
    }
    return goal === 0 ? true : false
}

var canJump = function(nums) {
    const size = nums.length
    const memoize = new Array(size).fill(false);
    memoize[0] = true;
    
    for (let i = 0; i < size; i++) {
        if(!memoize[i]) return false
        const furthestJump = Math.min(i+ nums[i], size - 1)
        for(let j= i+1; j<=furthestJump; j++){
            memoize[j] = true
        }
    }
    return true
}

:::

<hr/>

### 東

Solution 1 -- Intuitive Solution

:::spoiler Code

// Time O(n) | Space O(1) -- n is the length of nums array
var canJump = function(nums) {    
    let minJumpNeed = 0;
    for(let i = nums.length - 2; i >= 0; i--) {
        if(nums[i] === 0 && minJumpNeed === 0) {
            minJumpNeed = 1;
            continue;
        }

        if(minJumpNeed) {
            minJumpNeed++;
            if(nums[i] >= minJumpNeed) {
                minJumpNeed = 0;
            }
        }
    }

    return minJumpNeed === 0;
};

:::
<br/>

Solution 2 -- Revised Solution

:::spoiler Code

// Time O(n) | Space O(1) -- n is the length of nums array
var canJump = function(nums) {    
    let maxReachIdx = nums[0];
    for(let i = 1; i < nums.length; i++) {
        if(nums[i] === 0 && maxReachIdx <= i) {
            return false;
        }

        if(nums[i] !== 0 && maxReachIdx < nums[i] + i) {
            maxReachIdx = nums[i] + i;
        }
    }
    return true;
}

:::

<hr/>

### Jessie

[](https://hackmd.io/_uploads/H1kfiSuUC.png)

:::spoiler Code

var canJump = function (nums) {

  let lastIndex = nums.length - 1;
  let maxJump = 0;

  if (lastIndex === 0) return true;

  for (let i = 0; i < lastIndex; i++) {

    maxJump = Math.max(maxJump, i + nums[i]);

    if (maxJump >= lastIndex) return true;  //  可以跳超過底
    if (maxJump <= i) return false; //  跳不動了, 而且跳不到底

  }

};

:::

<hr/>

### Howard

:::spoiler Code

class Solution:
    def canJump(self, nums: List[int]) -> bool:

        # idea: car with gasoline
        # time O(n)
        # space O(1)
        # 每格 value 都當作加油站，只有在油用完時才 return False
        gas = 0
        for n in nums:
            if gas < 0:
                return False
            elif n > gas:
                gas = n
            gas -= 1
        return True

:::

<hr/>

<br>

## Live Coding

:::spoiler (name)

// write your code here

:::