DEV Community is a community of 751,566 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Posted on • Originally published at alkeshghorpade.me

LeetCode - Jump Game

Problem statement

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Problem statement taken from: https://leetcode.com/problems/jump-game

Example 1:

``````Input: nums = [2, 3, 1, 1, 4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
``````

Example 2:

``````Input: nums = [3, 2, 1, 0, 4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
``````

Constraints:

``````- 1 <= nums.length <= 10^4
- 0 <= nums[i] <= 10^5
``````

Explanation

Brute force approach

A naive approach is to start from the first element and recursively call for all the elements reachable from this first element. We can use the below approach to solve the problem.

``````minJumps(start, end) = Min ( minJumps(k, end) ) for all k reachable from start
``````

A small C++ snippet of the above approach will look as below:

``````int minJumps(int arr[], int n){
if (n == 1)
return 0;

int res = INT_MAX;
for (int i = n - 2; i >= 0; i--) {
if (i + arr[i] >= n - 1) {
int sub_res = minJumps(arr, i + 1);
if (sub_res != INT_MAX)
res = min(res, sub_res + 1);
}
}

return res;
}
``````

Since there are n maximum possible ways to move from an element, the time complexity of the above approach is O(N^2).

Optimized solution

The problem can be solved in linear time. We need to identify what's the maximum jump we can take from the current index i. Only if the current jump is greater than the maximum jump we use that index and increment the count.

Let's check the algorithm below:

``````- set max = nums[0] the first element of the array.

- if nums.size() == 1 && nums[0] == 0
- return true

- loop for i = 0; i < nums.size(); i++
- if max <= i && nums[i] == 0
- return false

- if i + nums[i] > max
- max = i + nums[i]

- if max >= nums.length - 1
- return true

- return false
``````

C++ solution

``````class Solution {
public:
bool canJump(vector<int>& nums) {
int max = nums[0];

if(nums.size() == 1 && nums[0] == 0)
return true;

for(int i = 0; i < nums.size(); i++){
if(max <= i && nums[i] == 0)
return false;

if(i + nums[i] > max)
max = i + nums[i];

if(max >= nums.size() - 1)
return true;
}

return false;
}
};
``````

Golang solution

``````func canJump(nums []int) bool {
max := nums[0]
length := len(nums)

if length == 1 && nums[0] == 0 {
return true
}

for i := 0; i < length; i++ {
if max <= i && nums[i] == 0 {
return false
}

if i + nums[i] > max {
max = i + nums[i]
}

if max >= length - 1 {
return true
}
}

return false
}
``````

Javascript solution

``````var canJump = function(nums) {
let max = nums[0];
const size = nums.length;

if( size == 1 && nums[0] == 0 ){
return true;
}

for(let i = 0; i < size; i++){
if( max <= i && nums[i] == 0 ){
return false;
}

if( i + nums[i] > max ){
max = i + nums[i];
}

if( max >= size - 1 ){
return size;
}
}

return false;
};
``````

Let's dry-run our algorithm to see how the solution works.

``````Input: nums = [2, 3, 1, 1, 4]

Step 1: max = nums[0]
= 2

Step 2: if nums.size() == 1 && nums[0] == 0
5 == 1 && 2 == 0
false

Step 3: loop for i = 0; i < nums.size()
0 < 5
true

max <= i && nums[i] == 0
2 <= 0 && nums[0] == 0
2 <= 0 && 2 == 0
false

i + nums[i] > max
0 + nums[0] > 2
0 + 2 > 2
false

max >= nums.size() - 1
2 >= 5 - 1
2 >= 4
false

i++
i = 1

Step 4: i < nums.size()
1 < 5
true

max <= i && nums[i] == 0
2 <= 1 && nums[1] == 0
2 <= 1 && 3 == 0
false

i + nums[i] > max
1 + nums[1] > 2
1 + 3 > 2
4 > 2
true

max = i + nums[i]
= 1 + nums[1]
= 1 + 3
= 4

max >= nums.size() - 1
4 >= 5 - 1
4 >= 4
true

return true

So the answer we return is true.
``````

Let's dry-run the negative test case.

``````Input: nums = [3, 2, 1, 0, 4]

Step 1: max = nums[0]
= 3

Step 2: if nums.size() == 1 && nums[0] == 0
5 == 1 && 3 == 0
false

Step 3: loop for i = 0; i < nums.size()
0 < 5
true

max <= i && nums[i] == 0
3 <= 0 && nums[0] == 0
3 <= 0 && 3 == 0
false

i + nums[i] > max
0 + nums[3] > 3
0 + 3 > 3
false

max >= nums.size() - 1
3 >= 5 - 1
3 >= 4
false

i++
i = 1

Step 4: i < nums.size()
1 < 5
true

max <= i && nums[i] == 0
3 <= 1 && nums[2] == 0
3 <= 1 && 2 == 0
false

i + nums[i] > max
1 + nums[2] > 3
1 + 2 > 3
3 > 3
false

max >= nums.size() - 1
3 >= 5 - 1
3 >= 4
false

i++
i = 2

Step 5: i < nums.size()
2 < 5
true

max <= i && nums[i] == 0
3 <= 2 && nums[2] == 0
3 <= 2 && 1 == 0
false

i + nums[i] > max
2 + nums[2] > 3
2 + 1 > 3
3 > 3
false

max >= nums.size() - 1
3 >= 5 - 1
3 >= 4
false

i++
i = 3

Step 6: i < nums.size()
3 < 5
true

max <= i && nums[i] == 0
3 <= 3 && nums[3] == 0
3 <= 3 && 0 == 0
true

return false

So the answer we return is false.
``````