Solution For Jump Game

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

Step by Step Implementation For Jump Game

class Solution {
    public boolean canJump(int[] nums) {
        //Greedy approach
        //Keep track of the furthest distance that can be reached
        //Starting from the first index, iterate through the array and update the furthest distance that can be reached
        //If the current index is greater than the furthest distance that can be reached, return false
        //Otherwise, return true
        
        int furthest = 0;
        for(int i=0; i furthest) {
                return false;
            }
            furthest = Math.max(furthest, nums[i]+i);
        }
        return true;
    }
}

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        
        # keep track of the furthest index we can reach
        max_index = 0
        
        # iterate through the array
        for i, num in enumerate(nums):
            
            # if the current index is greater than the furthest index we can reach, return False
            if i > max_index:
                return False
            
            # update max_index to be the greater of the two values (the current value or the current index + the value at the current index)
            max_index = max(max_index, i + num)
            
        # return True if we can reach the end of the array
        return True

var canJump = function(nums) {
    // Set up a variable to keep track of the furthest we can jump
    let max = 0;
    
    // Iterate through the array
    for (let i = 0; i < nums.length; i++) {
        // If the current index is greater than the furthest we can jump, return false
        if (i > max) {
            return false;
        }
        // Update max to be the furthest we can jump from the current index
        max = Math.max(i + nums[i], max);
    }
    
    // If we reach the end, return true
    return true;
};

class Solution {
public:
    bool canJump(vector& nums) {
        int n = nums.size();
        int reach = 0;
        for (int i = 0; i < n; ++i) {
            if (i > reach || reach >= n - 1) break;
            reach = max(reach, i + nums[i]);
        }
        return reach >= n - 1;
    }
};

public class Solution {
    public bool CanJump(int[] nums) {
        // keep track of the furthest index that can be reached
        int maxReach = 0;
        // iterate through the array
        for (int i = 0; i < nums.Length; i++) {
            // if the current index can't be reached, return false
            if (i > maxReach) {
                return false;
            }
            // update the furthest index that can be reached
            maxReach = Math.Max(maxReach, i + nums[i]);
        }
        // if the loop finishes, then all indices are reachable, so return true
        return true;
    }
}