55 Jump Game i && 45 Jump Game ii

Jump Game

Problem statement:

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Analysis:

There are two solutions for this problem, one is greedy, another is dynamic programming. The main difference is the direction.

Solution one: 

Greedy is the best solution for this problem, it is always forwarding(AC) O(n).

• Loop the whole array
• Keep a right most position where I can get, update it at each index. 
• if right most position is always greater than current index or it is already exceed the last position of array, return true since we can get the last position
• Once current index is greater than right most position, return false, since there is already no way to get there.

The code is as following:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.empty()){
            return false;
        }
        
        // keep a indicator for current right most position we can reach
        int right_most = 0;
        
        // loop to enumrate all elements
        for(int ix = 0; ix < nums.size(); ix++){ 
            // if current element already exceed the right most position
            // return false
            if(right_most < ix){
                return false;
            } else {
                // we already could reache the last element
                if(ix + nums[ix] >= nums.size() - 1){
                    return true;
                } else {
                    // otherwise, update the right most position
                    right_most = max(ix + nums[ix], right_most);
                }
            }
        }
        return false;
    }
};

Solution two(NOT AC):

Dynamic programming O(n*n)

For dynamic programming, we looks back, for each element, we enumerate all the element whose index is lower than it, and check if it is reachable.

class Solution {
public:
    // dynamic programming solution
    bool canJump(vector<int>& nums) {
        if (nums.empty()) {
            return false;
        }
        int size = nums.size();
        vector<bool> true_table(size, false);
        true_table[0] = true;
        for(int i = 1; i < nums.size(); i++){
            for(int j = 0; j < i; j++){
                if(true_table[j] && nums[j] + j >= i){
                    true_table[i] = true;
                    break;
                }
            }
        }
        return true_table[size - 1];
    }
};

--------------------------------- divide line --------------------------------------------

Jump Game ii

Problem Statement:

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

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.)

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

Analysis:

The main difference between jump game i && ii is that we should keep a minimum jump array for each element and update it for each element.

Solution one: Greedy

This is the accepted solution.

Solution two: Dynamic programming(NOT AC)

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }
        int size = nums.size();
        vector<bool> can_jump(size, false);
        vector<int> min_jump(size, INT_MAX);
        // initialize start status
        can_jump[0] = true;
        min_jump[0] = 0;
        // dynamic programming
        for(int i = 1; i < nums.size(); i++){
            for(int j = 0; j < i; j++){
                if(can_jump[j] && nums[j] + j >= i){
                    can_jump[i] = true;
                    min_jump[i] = min(min_jump[i], min_jump[j] + 1);
                }
            }
        }
        // return end status
        return min_jump[size - 1];
    }
};

Solution two: Greedy(AC)

we keep two variables, the first one is the most right position in current jump, the second one is the right most position in next jump.

Just one loop to get the final solution:

class Solution {
public:
    int jump(vector<int>& nums) {
        // initialize 
        if(nums.size() < 2){
            return 0;
        }
        // variables
        int cur_jump_right_most = nums[0];
        int next_jump_right_most = 0;
        int min_jump = 1;
        if(cur_jump_right_most >= nums.size() - 1){
            return min_jump;
        }
        // O(n)
        for(int ix = 1; ix < nums.size(); ix++){
            if(ix > cur_jump_right_most){
                // at boundary 
                // update the cur_jump_right_most position before next_jump_right_most
                cur_jump_right_most = next_jump_right_most;
                min_jump++;
            }
            next_jump_right_most = max(next_jump_right_most, nums[ix] + ix);
            if(next_jump_right_most >= nums.size() - 1){
                return ++min_jump;
            }
        }
        return min_jump;
    }
};