# Java(Time:O(n), Space:O(1)): With clear and easy understanding comments

• Thanks to all the discussions a lot. I have read some posts and I find it may still is a little hard to understand the underlying design philosophy. So I hope this code can help a little.

``````    public int jump (int[] nums) {
if (nums.length == 1) {//when length==1, ignore what's in nums[0]
return 0;
}

int step = 0;//init step = 0 before actual start
int position = 0;//start position in current step
int reachable = 0;//furthest can reach in current step
int furthest = 0;//furthest can reach in next step, it will be new reachable in next loop

//the loop invariant is the reachable corresponding to every step
while (position <= reachable) {//one loop indicate one step, it starts with step==0
furthest = Math.max(furthest, position + nums[position]);//get furthest for next loop
if (furthest >= nums.length - 1) {//can reach the end in next step
return step + 1;
}
if (position == reachable) {//this step end
if (furthest <= reachable) {//can not go further
return -1;
} else {//add this step and go further
++step;
reachable = furthest;
}
}
++position;//continue this step
}
return -1;
}``````

• A array like 5,4,3,2,1,5,4,3,2,1, I think Time is O(nm)

• I don't know whether we got different understanding about the "n" in O(n), which I indicate the length of the nums[] array.
Notice the code

``````++position;//continue this step
``````

at the last but one line. Every single loop will increase position. So at the worst case, the time consume will equal the length of the array.
And for your case, when the code reach the second "5", it should be return 2 and finish.Am I right?

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