C# simple, greedy, and optimized


  • 0
    D

    This one was fun. I went from an O(N^2) algorithm to O(N) and learned how to be "greedy" :-)

    Here the difference from the other posts is that in for loop, the condition is optimized. If we are going to check two conditions in the for loop, why not make sure those are optimal? I believe the code is still readable but now the loop condition is optimized.


    /// <summary>
    /// Given an array of non-negative integers, you are initially positioned at 
    /// the first index of the array. Each element in the array represents your 
    /// maximum jump length at that position. Determine if you are able to reach
    /// the last index.
    /// </summary>
    /// <example>
    /// A = [2,3,1,1,4], return true.
    /// A = [3,2,1,0,4], return false.
    /// </example>
    public class Solution
    {
        public bool CanJump(int[] nums)
        {
            int maxJump = 0, lenMinus1 = nums.Length - 1;
    
            for (int i=0; maxJump>=i && maxJump < lenMinus1; i++)
            {              
                if (i + nums[i] > maxJump)
                {
                    maxJump = i + nums[i];//if Ai=0, maxJump = i
                }
            }
    
            return maxJump >= lenMinus1;
        }
    }

Log in to reply
 

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