## Question

>[45. Jump Game II](https://arc.net/l/quote/krdlhtfz)

<br>

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

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

:::

<br>

## Thoughts & Solutions

### YC
:::spoiler Code

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    let currMax = 0;
    let nextMax = 0;
    let count = 0;
    /**
                [2,3,1,1,4]
        i        0 1 2 3 4
        cur 0    2 2 2
        nex 0    2 4 3
        cnt 0    1   2
    */

    for(let i = 0; i < nums.length - 1; i++){
        nextMax = Math.max(nextMax, i + nums[i]);
        if(i === currMax){
            currMax = nextMax;
            count++;
            if(nextMax === nums.length - 1) break;
        }
    }
    return count;
};

:::

<hr/>

### Sol


:::spoiler Code

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    let step = 0;
    let curEnd = 0;
    let furthestIndex = 0;
    for (let i = 0; i < nums.length -1; i++) {
        furthestIndex = Math.max(furthestIndex, i + nums[i]);
        if(i === curEnd) {
            step++
            curEnd = furthestIndex;
            if(furthestIndex>= nums.length -1) break;
        }
    }
    return step;
};

:::

<hr/>

### 東

:::spoiler Code

// Time O(n^2) | Space O(n) - n is the length of input nums array
var jump = function(nums) {
    const reversedJumpIndices = [nums.length - 1];
    for(let i = nums.length - 2; i >= 0; i--) {
        while(reversedJumpIndices.length >= 2) {
            if (nums[i] + i >= reversedJumpIndices[reversedJumpIndices.length - 2]) {
                reversedJumpIndices.pop();
            } else {
                break;
            }
        }
        reversedJumpIndices.push(i);
    }

    return reversedJumpIndices.length - 1;
};

:::

<hr/>

### Jessie

[](https://hackmd.io/_uploads/rJVZLwOLA.png)
:::spoiler Code

var jump = function (nums) {

    let index = countStep = 0;
    let lastIndex = nums.length - 1;

    while (lastIndex !== 0) {
        if (index + nums[index] >= lastIndex) {
            lastIndex = index;
            countStep++;
            index = 0;
            continue;
        }
        index++;
    }
    return countStep;

};

:::

<hr/>

### Howard

:::spoiler Code

class Solution:
    def jump(self, nums: List[int]) -> int:
        # 暴力解
        # time: O(n^2)
        # space: O(n)
        
        # for example: [2,3,1,1,4]
        # min_steps:
        # [0, 5, 5, 5, 5]
        # [0, 1, 1, 5, 5]
        # [0, 1, 1, 2, 2]
        # [0, 1, 1, 2, 2]
        # [0, 1, 1, 2, 2]
        # [0, 1, 1, 2, 2]
        # result: 2
        n = len(nums)
        min_steps = [n] * len(nums)
        min_steps[0] = 0

        step = 0
        for i in range(n):
            step = min_steps[i] + 1
            for j in range(i+1, min(n, i + nums[i] + 1)):
                min_steps[j] = min(min_steps[j], step)
        return min_steps[n-1]

:::

<hr/>

### Haoyu

:::spoiler Code

var jump = function(nums) {
    let jump = 0;
    let curEnd = 0;
    let curFarthest = curEnd + nums[curEnd];

    while (curEnd < nums.length - 1) {
        jump += 1;

        if (curFarthest < nums.length - 1) {
            let [nextEnd, nextFarthest] = [curEnd, curFarthest];

            for (let j = curEnd + 1; j < curFarthest + 1; j += 1) {
                const farthest = j + nums[j];

                if (farthest > nextFarthest) {
                    [nextEnd, nextFarthest] = [j, farthest];
                }
            }

            [curEnd, curFarthest] = [nextEnd, nextFarthest];
        } else curEnd = curFarthest;
    }

    return jump;
};

:::

<br>

## Live Coding

:::spoiler (name)

// write your code here

:::