# My O(n) time O(1) space Solution.

• Only one pass. O(n) time O(1) memory.

public class Solution {

``````public int jump(int[] A) {
if (A == null || A.length <= 1) {
return 0;
}

int tail = A[0];
int min = 1;
int begin = 0;
while (tail < A.length - 1) {
int maxPace = 0;
for (int i = begin ; i <= tail; i++) {
maxPace = Math.max(maxPace, i + A[i]);
}
begin = tail + 1;
tail = Math.max(tail, maxPace);
min++;
}
return min;
}
``````

}

• Sorry, this is a very nice and neat solution!!

• Why do set
begin = tail + 1
before
tail = Math.max(tail, maxPace)?

• Max(tail,maxPace) is not necessary, just set tail=maxPace

• I kind of like starting from 0 instead of 1, sort of less looking like less "edge cases"

``````  public class Solution {
public int jump(int[] A) {
if (A == null   ) return 0;
int begin = 0;
int tail = 0;
int steps = 0;
while(tail < A.length-1) {
int maxPace = 0;
for(int i=begin;i<=tail;i++) {
maxPace = Math.max(maxPace, i+A[i]);
}
begin = tail +1;
tail = maxPace; // this means we walked one more step
steps ++;
}

return steps;
}
}
``````

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