O(n) C++ solution, a slow solution yet easy to understand logic. Explanation provided.


  • 0
    S

    The basic idea here is that you start traversing until the jump length of each element, in the process you also check for each element the maximum index that can be reached and proceed appropriately..

    class Solution {
    public:
    	int jump(vector<int>& nums) {
    		if (nums.size() == 1)
    			return 0;
    		int index = 0;
    		int jumps = 0;
    		int n = nums.size() - 1;
    		int min;
    		for (int i = 0; i<nums.size() - 1;) {
        //To see if the element at i'th position can reach the end of the array.
    			if (n - (nums[i]+i) <= 0) {
    				jumps++; break;
    			}
    			//To store the step size at index i.
    			int steps = nums[i];
    			vector<int> len;
    			min=INT_MIN;
    			for (int k = i + 1; k <= steps + i; k++) {
    //calculates the position in the array that can jump to the furthest position.
    			    if(k+nums[k]>=min){
    			        min=k+nums[k];
    			        index=k;
    			    }
    			}
    			//update the value of i to that index.
    			i = index;
    			jumps++;
    		}
    		
    		return jumps;
    	}
    };
    

Log in to reply
 

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