Intuition

Every time, when meeting the farthest position, we will need another jump.

Specifically, check if you can reach then jump number += 1,
If reach the end, jump number += 1, end=farthest
Edge case is if only has <=1 elements need to jump 0 times to the end.

Approach

• We are using a search algorithm that works by moving forward in steps and counting each step as a jump.

• The algorithm keeps track of the farthest reachable position at each step and updates the number of jumps needed to reach that farthest position.

• The algorithm returns the minimum number of jumps needed to reach the end of the array.

Complexity

• Time complexity: O(n)

• Space complexity: O(1)

Code

class Solution {
    public int jump(int[] nums) {
        int ans = 0;
        int end = 0;
        int farthest = 0;
        int n = nums.length;
        // BFS
        if (n == 1){
            return 0;
        }
        for (int i=0; i<n; i++){
            farthest = Math.max(farthest, i+nums[i]);
            if (farthest >= n - 1){
                ans += 1;
                break;
            }
            if (i == end)
            {
                ans += 1;
                end = farthest;
            }    
        }
        return ans;
    }
}

class Solution:
    def jump(self, nums: List[int]) -> int:
        ans = 0
        end = 0
        farthest = 0
        n = len(nums)
        if (n == 1){
            return 0;
        }
        # BFS
        for i in range(n-1):
            farthest = max(farthest, i + nums[i])
            if farthest >= n - 1:
                ans += 1
                break
            if i == end:
                ans += 1
                end = farthest
        return ans