Jump Game - Leetcode Solution

Problem Statement:

You are given an array of non-negative integers nums, where each element represents your maximum jump distance at that position. Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

Example:

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.

Solution:

The problem is to find the minimum number of jumps required to reach the last index. We can solve this problem using the greedy approach

1. Initialize the variables: currEnd=0, currFarthest=0, and the number of jumps=0
2. Iterate through the array from the first element to the last element
3. For each element in the array: a. Update the currFarthest to max(currFarthest, nums[i]+i) b. If i == currEnd, update currEnd=currFarthest and increment the number of jumps by 1
4. Return the number of jumps.

Dry Run:

Let’s dry run the above approach with the given example

nums = [2,3,1,1,4]

currEnd = currFarthest = jumps = 0

Iteration 1: nums[0]=2 currFarthest = max(0+2,0) = 2 Iteration 2: nums[1]=3 currFarthest = max(2+3,2) = 5 Iteration 3: nums[2]=1 currFarthest = max(5+1,3) = 6 Iteration 4: nums[3]=1 currFarthest = max(6+1,4) = 7 currEnd = 3, jumps=1 Iteration 5: nums[4]=4 currFarthest = max(7+4,5) = 11 currEnd = 7, jumps=2

Final value of jumps = 2

Time complexity: O(n)

Code:

def jump(nums): currEnd = currFarthest = jumps = 0 for i in range(len(nums)-1): currFarthest = max(currFarthest, i + nums[i]) if i == currEnd: jumps += 1 currEnd = currFarthest return jumps

1