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

Dry Run

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.