C# alternative O(n) solution with explanation


  • 0
    A

    Idea: Abusing the fact that player cannot reach last index, if they meet 0 or negative number on the way, and cannot jump/skip over that particular index. Hence to resolve this:

    1. Looping from end of array, and find "0 or negative number"
    2. To check if the player is able to jump surpasses the index of the said "0 or negative number"
    public class Solution {
        public bool CanJump(int[] nums) {
        
            bool zero_found = false;
            int index_zero = nums.Length-1;
            
            for(int i=nums.Length-2; i>=0;i--)
            {
                if(zero_found)
                {
                    if(nums[i] > index_zero-i)
                    {
                        zero_found = false;
                    }
                }
                
                if(nums[i] <= 0 && !zero_found)
                {
                    zero_found = true;
                    index_zero = i;
                }
            }
            
            return !zero_found;
        }
    }
    

Log in to reply
 

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