0045 - Jump Game II (Medium)

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Input: nums = [2,3,0,1,4]
Output: 2

// intuition:
// we can image the input as graph.
// in example 1, starting from the root, we can reach the 2nd node and 3rd node
// from the 2nd node, we can reach 3rd, 4th, and 5th
// from the 3rd node, we can reach 4th
// from the 4th node, we can reach 5th
// from the 5th node, it is the desination, we don't need to jump
// here we can put those on different level, i.e.
// lv1: 2
// lv2: 1 3
// lv3: 1 4
// each level can be reachable from the previous level starting from 2nd level
// each level contains the possible length of jump
// the minimum number of jumps is the jump required to make from level 1

class Solution {
public:
    int jump(vector<int>& nums) {
        // cur_end: the ending index of the current level
        // nxt_end: the ending index of the next level
        int n = nums.size(), cur_end = 0, nxt_end = 0, steps = 0;
        for (int i = 0; i < n; i++) {
            // if the current index is out of the current level,
            // we add 1 step because we are going to the next level
            if (i > cur_end) steps += 1, cur_end = nxt_end;
            // update nxt_end - take the max index
            nxt_end = max(nxt_end, i + nums[i]);
        }
        return steps;
    }
};

# intuition:
# we can image the input as graph.
# in example 1, starting from the root, we can reach the 2nd node and 3rd node
# from the 2nd node, we can reach 3rd, 4th, and 5th
# from the 3rd node, we can reach 4th
# from the 4th node, we can reach 5th
# from the 5th node, it is the desination, we don't need to jump
# here we can put those on different level, i.e.
# lv1: 2
# lv2: 1 3
# lv3: 1 4
# each level can be reachable from the previous level starting from 2nd level
# each level contains the possible length of jump
# the minimum number of jumps is the jump required to make from level 1


class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
		# cur_end: the ending index of the current level
		# nxt_end: the ending index of the next level
        cur_end, nxt_end = 0, 0
        steps = 0
        for i in range(n):
			# if the current index is out of the current level,
			# we add 1 step because we are going to the next level
            if i > cur_end:
                steps += 1
                cur_end = nxt_end
            # update nxt_end - take the max index
            nxt_end = max(nxt_end, i + nums[i])
        return steps

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function (nums) {
  let steps = 0;
  let currEnd = 0,
    maxEnd = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > currEnd) {
      steps++;
      currEnd = maxEnd;
    }
    maxEnd = Math.max(maxEnd, i + nums[i]);
  }
  return steps;
};