# Share my greedy solution, starting from last Index

• Start from last index. For each step, find the smallest index it can jump from and then update the last index until last index reaches zero.

``````public class Solution {
public int jump(int[] nums) {
int lastIndex = nums.length - 1;
int step = 0;
int i;

while (lastIndex != 0) {
for (i = 0; i < lastIndex; i++)
if (i + nums[i] >= lastIndex)
break;
if (i == lastIndex)
return -1;
lastIndex = i;
step++;
}

return step;
}
}``````

• I ' d like to show everyone one of my fool solution, to reminded me do not makes such fool mistake!
I have the same mind with you, but I search the samllest one from the index to 0. It works fine when the testcase was small,but time limited when the test case is 25000's one.

``````int jump(vector<int>& nums) {
if(nums.empty()) return 0;
int n = nums.size(), ans = 0, index = n-1, next = -1;
while(index>0) {
for (int i = index-1; i >=0 ; i--)
{
if(nums[i] >= index-i) next = i;
// cout<<nums[i]<<","<<index-i<<endl;
}
index = next;
// cout<<index<<endl;
ans++;
}
return ans;
}``````

but your answer also time limited.when the test case was 25000's one.

• Time limited，it‘s O(N^2).

• Yes, you are right. I found the problem and so it's necessary to start from zero and to record the last farthest index.

• Yes, I have realized the problem. Actually it's O(n^2). So it's necessary to start from zero and record the last farthest index.
But I thought this approach may be easy to understand...

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