Greedy, 14ms. O(n), O(1), easy C++ solution, easy understanding.


  • 11
    R
    bool canJump(int A[], int n) { // Greedy
        
        n==1?({return true;}):({;});  // Return true if already reach the end
        
        int max_index_can_jump = 0; // So far the current max index we can jump to.
        
        for (int i = 0; i <= max_index_can_jump; ++i )
        {
            if( (A[i]+i) > max_index_can_jump ) // check if need to update the current max index we can jump to
            {
                if((A[i]+i) >= (n - 1)) // check if we can jump to the last index (end)
                {
                    return true;
                }
                else
                {
                    max_index_can_jump = A[i]+i; // Then update
                }
            }
        }
        
        //return max_index_can_jump == (n-1); // First line is only one of the case
        
        return false;
    }

  • 1
    V
    /// C# solution inspired by this code. trying to make it simpler and easy to understand.
    
    public class Solution {
            
            public bool CanJump(int[] A) {
                
                /// if n = 1,0 always returning true.
                /// this case will be handled automatically, 
                /// but to be clear adding this condition
                if(A == null || A.Length <= 1) return true;
                
                int N = A.Length;
                int maxIndexReachable = 0; /// 0 is always reachable!
        
                /// Loop stops if last index is already reachable e.i: max_index_can_jump >=n 
                for (int i = 0; i <= maxIndexReachable && maxIndexReachable < N-1; ++i )
                {
                    if( (A[i]+i) > maxIndexReachable ) /// if using this element farther than current max index can be reached
                    {
                         maxIndexReachable = A[i] + i; /// then update current max max_index_can_jump
                    }
                }
        
                return maxIndexReachable >= (N-1); /// finally if maxIndexReachable is N-1 or higher
            }
        }

  • 0
    A

    -1 for this: n==1?({return true;}):({;});


Log in to reply
 

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