# 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;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]