Solution


  • 0
    Z

    I have created two solutions for this problem, the first one was finding the fewest steps that's required to reach the destination (end of the array) for each nodes, which would solve this problem. However, I wasn't able to submit that one because it would fail at one test case which has many many nodes with execution time exceeded.

    This is the second solution I created, it is pretty simple, which simply finds the quickest path to the destination from any given node (in this case node 0). And here's the solution:

    class Solution {
    public:
        int jump(vector<int>& nums) {
            int currentIndex = 0;
            int currentStepCount = 0;
            
            if(nums.size() == 1)
            {
                // A shortcut for optimization purpose
                return 0;
            }
            
            while(true)
            {
                if(currentIndex >= nums.size())
                {
                    // We have already reached or passed our destination
                    break;
                }
                else if(currentIndex + nums[currentIndex] >= nums.size()-1)
                {
                    // We know we will reach our destination in the next move
                    currentStepCount++;
                    break;
                }
                
                currentIndex = currentMaximumReach(nums, currentIndex);
                currentStepCount++;
            }
            
            return currentStepCount;
        }
        
        int currentMaximumReach(vector<int> nums, int index)
        {
            //
            // This function returns the index of the next node that will give the maximum reach from the current node
            //
    
            int MaxReach = index+nums[index];
            int MaxReachNode = index;
            
            for(int i = 1; (i+index < nums.size()) && (i <= nums[index]); i++)
            {
                if(nums[index+i]+index+i > MaxReach)
                {
                    MaxReach = index+i+nums[index+i];
                    MaxReachNode = index+i;
                }
            }
            
            // Return the node that would give the max reach from the current node
            return MaxReachNode;
        }
    };
    

Log in to reply
 

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