[LeetCode/Python] 45. Jump Game II

📌 Problem

45. Jump Game II

📌 Solution

1. Dynamic Programming Approach

Idea

Computer the minimum number of jumps needed to reach each stage

1. Define Subproblem:
   opt[i] = = minimum number of jumps to reach stage i

   • j = all previous indices that can directly reach i
   • opt[i] = minimum of opt[j] + 1

2. Initialization:

   • opt[0] = 0
   • opt[i] = infinity for all i

3. Pseudocode:

   for i = 1 to n-1:
       for j = i-1 to 0:
           if nums[j] >= i - j:
               OPT[i] = min(OPT[i], OPT[j] + 1)
   endfor

4. Result:
   • Return opt[n-1], the minimum jumps needed to reach the last index

Code

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)

        # opt[i] = minimum number of jumps to reach stage i
        opt = [float('inf')] * n
        opt[0] = 0

        for i in range(1, n):
            for j in range(i, -1, -1):
                if nums[j] >= i - j:
                    opt[i] = min(opt[i], opt[j] + 1)

        return opt[n-1]

Complexity

• Worst Case Time Complexity: $O(n^2)$

  • Outer loop over i (from 1 to n-1) -> $n$
  • Inner loop potentially checks all j < i -> $n$

• Space Complexity: $O(n)$ (DP array of size $n$)

2. Greedy Approach

Idea

Traverse the array once, keeping track of:

• end: the furthest index reachable with the current jump count
• farthest: the furthest index reachable with one more jump
• Whenever the current index reaches end, increment jump count and update end = farthest

Code

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return 0

        jumps = 0
        end = 0          # current range end
        farthest = 0     # farthest reachable next

        for i in range(n - 1):
            farthest = max(farthest, i + nums[i])
            if i == end:           # end of current range
                jumps += 1
                end = farthest
                if end >= n - 1:   # last index covered
                    break

        return jumps

Complexity

• Time Complexity: $O(n)$ (Single pass over the array)
• Space Complexity: $O(1)$ (Only a few pointers (jumps, end, farthest))