How can my solution prevent StackOverFlow?


  • 0

    When a big array is given, StackOverFlowError occurs.

    	public boolean canJump(int[] nums) {
    		if (nums == null || nums.length <= 1) {
    			return true;
    		}
    		return canJumpAt(nums, 0);
    	}
    
    	private boolean canJumpAt(int[] nums, int index) {
    		if (index + nums[index] >= nums.length - 1)
    			return true;
    
    		if (nums[index] <= 0)
    			return false;
    
    		for (int jump = nums[index]; jump > 0; jump--) {
    			if (canJumpAt(nums, index + jump)) {
    				return true;
    			}
    		}
    
    		nums[index] = -1;
    		return false;
    	}
    

  • 0

    @dale.seo
    You just do a typical wrong checking here. Actually you should select the possible longest step within the range of the current position instead of checking each possible step which will definitely encounter TLE or StackOverFlow in big case.

    Check one of my solutions in C++ as follows:

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

  • 0

    @LHearen Thank you for your helpful advice. I just submitted new code and it got accepted. :smile:


  • 0
    S

    @Dale-Seo I have a stack overflow too, can you please help me.

    class Solution {
    public:
    	int flag = 0;
    	set<int> s;
    	void jumping(vector<int>& nums,int index) {
    		if (flag)
    			return;
    		if (index < 0)
    			return;
    		if (index >= nums.size() - 1) {
    			flag = 1;
    			return;
    		}
    		if (s.find(index) != s.end())
    			return;
    		else
    			s.insert(index);
    
    		if (nums[index]) {
    			for(int i=nums[index];i>0;i--){
    			    jumping(nums,i+index);
    			}
    		}
    	}
    	bool canJump(vector<int>& nums) {
    		jumping(nums, 0);
    		if (flag)
    			return 1;
    		return 0;
    	}
    };
    

  • 0

    @sujiths52 Your solution is really in a mess, read solutions of others if you are stuck in there.


  • 0
    S

    @LHearen Okay, I m doing so.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.