55. Jump Game : LeetCode Step-by-Step Approach

Jump Game - LeetCode

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.

Photo by Jess Bailey on Unsplash

APPROACH:

STEP 1: Create an empty vector ‘nums’ to store integers. Use a loop that runs five times (i.e., i goes from 0 to 4) to read input integers from the user and push them into the ‘nums’ vector.

STEP 2: Calculate the initial value of the ‘index’ variable, which represents the rightmost index in the ‘nums’ vector. The ‘index’ is initialized as the size of the ‘nums’ vector minus one (indexing is 0-based in C++).

STEP 3: Use a second loop that iterates from the end of the ‘nums’ vector to the beginning (i goes from nums.size() — 1 to 0, both inclusive).

STEP 4: In each iteration of the second loop, check if the current element ‘nums[i]’ plus ‘i’ (i.e., the value of the element plus its index) is greater than or equal to the ‘index’ value.

STEP 5: If the condition ‘nums[i] + i >= index’ is true, update the ‘index’ variable to ‘i’. This means that the current index ‘i’ becomes the new rightmost index that can be reached by adding the value of the element at that index to the index itself.

STEP 6: After the second loop is complete, the ‘index’ variable will hold the leftmost index that can be reached in one or more steps from the initial rightmost index.

STEP 7: Check if the ‘index’ is equal to 0. If ‘index’ is 0, it means that the leftmost index (index 0) can be reached from the initial rightmost index. In this case, print “true” as the output. Otherwise, print “false” as the output.

This problem is commonly known as the “Jump Game” problem. The code uses a greedy approach to find the minimum number of jumps required to reach the end of the array, starting from the first element. It updates the rightmost reachable index as it iterates through the array from right to left. If the rightmost reachable index eventually reaches the beginning of the array (index 0), it means that the end of the array can be reached from the beginning, and the output is “true”. Otherwise, the output is “false”.

#include<bits/stdc++.h>
using namespace std;

int main(){

   vector<int>nums;

   int i,a;

   for(i=0; i<5; i++){
    cin>>a;
    nums.push_back(a);
   }

   int index = nums.size() - 1;
   
   for (int i = nums.size() - 1; i >= 0; i--) {
            if (nums[i] + i >= index) {
                index = i; 
            }
    }

    if (index == 0) {
            cout<<"true";
    } else {
            cout<<"false";
    
    }
    return 0;
}

        

TIME COMPLEXITY: O(N).

SPACE COMPLEXITY: O(N).

Hope you find this helpful!😊