1
\$\begingroup\$

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.
\$\endgroup\$
1
  • \$\begingroup\$ Looks valid, the bounds on complexity tight. I'd neither call it greedy nor dynamic programming. One greedy solution would look for possible jump starts starting from current target down, immediately replacing current target. Returning 0 is a possible start. \$\endgroup\$
    – greybeard
    Oct 10, 2022 at 6:31

2 Answers 2

4
\$\begingroup\$

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.

\$\endgroup\$
-1
\$\begingroup\$

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;
     }
 }

 
\$\endgroup\$
2
  • 4
    \$\begingroup\$ please explain why your alternative approach is better than the OP's solution. The goal is to review the OP's solution \$\endgroup\$ May 5 at 8:59
  • \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process. \$\endgroup\$
    – Mast
    May 6 at 7:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.