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

Answer 1

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.