DAY 8 - Jump Game

Hello to anyone reading this. I am still relatively new to coding and this platform as well, so please feel free to drop any corrections/advice for me.
I am trying to do the 100 Day-Challenge of consistent coding and this is Day 8.Looking forward to a positive interaction with all of you.

Today we are going to do a rather famous question. Well it's one of my all time favourites.

DAY 7 Problem 1: 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.

Approach:

Although we can take many approaches to this question such as using basic recursion and using DP with recursion. We are going to solve this question using greedy approach.
Let's note down the observations first.

Let's assume we have a finger at the starting index and the max jump is index's value. The value our finger can point maximum is that index + index[value]. We just need to make sure when we are going through the array if the final position or our goal is ever in our reach.

Hence we are being greedy and not worrying if we are able to reach the final position. We are just worrying if we can reach any position than the current index we can reach.

Code:

bool canJump(vector<int>& nums) {
        if(nums.size() == 1)
        {
            return true;
        }
        if(nums[0] == 0)
        {
            return false;
        }
        int reach = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            if(reach < i)
            {
                return false;
            }
            reach = max(reach, i + nums[i]);
        }
        return true;
    }

Let's do a dry run of our approach on Example 2: for better understanding.

• At the start we are at index 0. Hence our reach is 0 as well.
• Then inside the loop our reach updates to (0 + nums[0]) which is basically 3.
• Our reach is index 3.
• Then traversing the array further , we see our max reach comes again to be the same index. Hence it is not updated but it does not return false as our reach is still greater than equal to our index.
• Then at the end of our loop our reach finally reaches at end when it finds that our reach(which basically stays at 3) is less than index(4).
• Hence it returns false.

I hope this example 2 helped in understanding the approach better.

This is it for today. Thanks for reading the post.