Leetcode Study Day 6

2023-09-23

Jump Game

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.

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 <= 104
0 <= nums[i] <= 105

Greedy solution

I try to solve this problem by greedy solution by myself but I failed. One solution is to use greedy method.

First, we initiate a variable called maxReach, which means how far can we jump from a specific index.

Then, we iterate the loop, in each iteration, we compare if the index is larger than the maxReach, if so, it means it cannot jump to the current index, we return false.

1 2	if (i > maxReach) return false;

Then we find the max value between maxReach and i + nums[i], the larger one will be the new value of maxReach

1	maxReach = max (maxReach, i + nums[i]);

If the vlaue of maxReach is larger than the length of the array, which means we can jump to the end of the array, we return true.

1 2	if (maxReach >= n - 1) return true;

Full code

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int maxReach = 0;
        for (int i = 0; i < n; i++){
            if (i > maxReach)
                return false;

            maxReach = max (maxReach, i + nums[i]);
            
            if (maxReach >= n - 1)
                return true;
        }
        return true;
    }
};

Jump Game II

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

1
2
3

0 <= j <= nums[i] and
i + j < n
Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:

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.
Example 2:

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

Constraints:

1 <= nums.length <= 104
0 <= nums[i] <= 1000
It's guaranteed that you can reach nums[n - 1].

Greedy solution

In this solution, we create a new vairable called currentPosition. When its value is equal to the index in the loop, it means a jump is needed, so we increase the count, and update the currentPosition to the maxJump, which means we need to jump when the index is equal to the current maxJump. Also, during the iteration, we update the maxJump by comparing the current maxJump with (i+nums[i]).

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int maxJump = 0;
        int currentPosition = 0;
        int count = 0;
        for (int i = 0; i < n-1; i++){
            maxJump = max(maxJump, i + nums[i]);
            if (currentPosition == i){
                currentPosition = maxJump;
                count ++;
            }
        }
        return count;
    }
};