# A Solution using GREEDY, But is it REALLY o(n)?

• The ideas is simple ,using some greedy tactics.

We generally maintain a start position to indicate the current position,and there are only 2 main steps for solving the problem.

step(1): When you are at position start, you can go to positon start + 1 to start + nums[start] if nums[start] > 0, and now you can know
whether you can go to the end by judging nums[start] >= nums.size()-1.If so, go to step(3). If not, go to step(2).

step(2): From start + 1 to start + nums[start], in these nums[start] positions,pick one to be the next start position. And the rule for picking is simple:

You pick a position start + i, from which you can move forward the longest distance,which means
i + nums[start + i] >= j + nums[start + j] for any 1 <= j <= nums[start].

So the start position is at start + i now. Then you go to the step(1).

Finished! But I still have some questions about this solution, what is its time complexity? Is it really o(n)?

``````class Solution {
public:
int jump(vector<int>& nums) {
if(nums.size() < 2)
return 0;
for(int start = 0, step = 1; ; step++){
if(start + nums[start] >= nums.size() - 1)
return step;
/* if(nums[start] == 0)
return false;  // doesn't need this for this problem's tests */
int maxDistence = 0, nextStart = start;
for(int i = 1; i <= nums[start]; i++){
if(i + nums[start + i] >= maxDistence){
nextStart = start + i;
maxDistence = i + nums[start + i];
}
}
start = nextStart;
}
}
};``````

• ``````public class Solution {
public int jump(int[] nums) {
int maximum = 0;
int nextMaximum = 0;
int count = 0;

for (int i = 0; i < nums.length-1; i++) {
nextMaximum = Math.max(nextMaximum,nums[i]+i);
if (i == maximum) {
count ++;
if (nextMaximum >= nums.length-1) {
return count;
}
maximum = nextMaximum;
}
}
return count;
}
``````

}

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