Jump Game Correction

Question

I'm not sure how to improve my solution for the jump game question (https://leetcode.com/problems/jump-game/description/) .It seems logically correct but I encounter a java.lang.Stackoverflow error for large inputs like [nums=[1,1,1,1,1,1,1,........]]

I know that I'm overflowing due to too many recursive calls , how can i optimize it ?

class Solution {
  public boolean canJump(int[] nums) {
    int []f = new int[1];
    f[0] = 0;
    return help(nums,0,f);
  }
  public static boolean help(int[]nums, int c, int[] f) {
    if(c==nums.length-1) {
      f[0] =1;
      return true;
    }
    if(f[0]==1) return true;
    int val = nums[c];
    for(int i = 1; i <= val; i++) {
      if(f[0]==1) return true;
      return help(nums,(c + i), f);
    }
    return false;
  }
}

The `int[] f` argument is a little confusing. If you need a flag you can use `AtomicBoolean`. Also it seems like your for loop is only executed once. — Judger, Nov 07 '17 at 01:44
int[] f is flag that gets passed by reference so I can cut down iterations once I've reached the end . I'll try learning about AtomicBoolean , will it be a pass by reference datatype , since I need to maintain the value across different calls. — Jaharsh, Nov 07 '17 at 01:54
The for loop gets executed once in each recursive call , overall n*n — Jaharsh, Nov 07 '17 at 01:55
I'm saying that in your for loop, `i++` is never executed because no matter what the method returns in the end of the first iteration when i=1 — Judger, Nov 07 '17 at 05:39
Nope , the above solution works perfectly fine for small inputs (tested) . The for loop with iterate each time the function comes back from its child call to the current call . You might wanna trace the calls if you are still confused . — Jaharsh, Nov 07 '17 at 05:51

score 0 · Answer 1 · answered Mar 02 '22 at 14:44

This can be solved in T:O(N) with greedy algorithm:

class Solution {
    public int jump(int[] nums) {
        int res=0, l=0, r=0;
        while(r<(nums.length-1)){
            int farthest=0;
            for (int i=l;i<r+1;i++){
                farthest=Integer.max(farthest,i+nums[i]);
            }
            l=r+1;
            r=farthest;
            res++;
        }
        return res;
    }
}

Explanation

  nums = [2,3,1,1,4]

you jump 2 steps. you get the index 2.so you are jumping elements [3,1]. Nov you loop through [3,1] and check which one will take you to the further. In this case it is 3. Then update the variables. Increase res=1

From element 3 which is index-1. you jump 3 steps, jumping [1,1,4]. Now loop through [1,1,4] find the farthest. which is 4. increase res=2. Since out of while loop, return res=2.

It seems to have two nested loops, but if you look carefully, total iteration is N.

Jump Game Correction

1 Answers1

Explanation