Leetcode 55. Jump Game solution

Question

I was working on Jump Game problem on leetcode

Question

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.

My Solution

// TC: O(N^2)
// SC: O(1)
var canJump = function(nums) {
    let targetIndex = nums.length -1;
    
    //We find the left most element (say 'x') which jumps to last element
    //Then we find the left most element that jumps to the above left most element 'x'
    while(targetIndex > 0){
        //Starting from left find the 1st elements that jumps to target element
        for(let i = 0; i < targetIndex; i++){
            //If element found update the target element as current index
            if(i + nums[i] >= targetIndex){
                targetIndex = i
                break
            }
            //If element previous to target element is also not valid than we don't have a solution
            if(i === targetIndex -1) return false
        }
    }
    
    return true
};

Wanted to clarify few things:

1. Is this a valid solution? It passes all the test cases on LC however I wanted to confirm my logic as I couldn't find any similar solution in answers.
2. Are the mentioned time and space complexities, \$O(N^2)\$ & \$O(1)\$ respectively correct?
3. If the solution is correct, what would call this approach? Is it greedy or dynamic programming? I don't understand the difference between the 2 right now.

Answer 1

Space complexity

The space complexity is \$O(1)\$: the storage of the variables used in the computation doesn't depend on the size of the input, it's constant.

Time complexity

The time complexity is \$O(n^2)\$. A simple example of the worst case is when the input is an array of 1 values. The outer loop runs n times, and the inner loop visits all elements from the start until n - 1 at first, then until n - 2, and so on.

Notice that it's inefficient to visit the elements from the start every time.

Consider this alternative algorithm that runs in \$O(n)\$:

var canJump = function(nums) {
    const target = nums.length - 1;
    let reachable = 0;

    for (let index = 0; index < nums.length && index <= reachable; index++) {
        reachable = Math.max(reachable, index + nums[index]);
        if (reachable >= target) return true;
    }
    
    return false;
};

Greedy algorithms and dynamic programming

A greedy algorithm:

• makes greedy choices to reach the solution
• does not reconsider choices already made, does not try to improve them
• does not consider all possible choices, and does not always find the solution

By contrast, dynamic programming (correctly done) is exhaustive, and always finds the solution.

See wikipedia's Greedy algorithm page for more details.

Answer 2

TC = O(N) SC = O(1) Iterates through the array, updating the maximum reachable index and decrementing the steps available. If it exhausts steps before reaching the end, it returns false; otherwise, it returns true if the last index is reachable.

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