Concise O(n) one loop JAVA solution based on Greedy

• Explanation

The main idea is based on greedy. Let's say the range of the current jump is [curBegin, curEnd], curFarthest is the farthest point that all points in [curBegin, curEnd] can reach. Once the current point reaches curEnd, then trigger another jump, and set the new curEnd with curFarthest, then keep the above steps, as the following:

``````public int jump(int[] A) {
int jumps = 0, curEnd = 0, curFarthest = 0;
for (int i = 0; i < A.length - 1; i++) {
curFarthest = Math.max(curFarthest, i + A[i]);
if (i == curEnd) {
jumps++;
curEnd = curFarthest;
}
}
return jumps;
}``````

• add some code to jump out early.

``````public class Solution {

public int jump(int[] A) {
int jumps = 0, curEnd = 0, curFarthest = 0;
for (int i = 0; i < A.length - 1; i++) {
curFarthest = Math.max(curFarthest, i + A[i]);
if (i == curEnd) {
jumps++;
curEnd = curFarthest;

if (curEnd >= A.length - 1) {
break;
}
}
}
return jumps;
}
}``````

• This program will fail when there is 0 in between.
For an example, consider the case: arr[] = {2,4,1,1,1,0,6}, ideally, we should not be able to reach end.

• This post is deleted!

• Note You can assume that you can always reach the last index.

• Thanks for sharing!

• @Moriarty Well, put your code here is better.

``````public int jump(int[] nums) {
int curEnd = 0, curFarthest = 0, steps = 0;
for (int i = 0; i < nums.length - 1; i++) {
curFarthest = Math.max(curFarthest, nums[i] + i);
if (curFarthest >= nums.length - 1) {
steps++;
break;
}
if (i == curEnd) {
steps++;
curEnd = curFarthest;
}
}
return steps;
}
``````

• @dakshvasistha the problem says "You can assume that you can always reach the last index."
But in your case, the last index could not be accessed.

• This post is deleted!

• How to deal with [0, 1] ?

• ``````// why we need i < length-1 ?
//  I think it's when we is at index 0, we don`t count the index.
// is it  right ??
for (int i = 0; i < A.length - 1; i++) {

``````

• Can someone please explain how to modify the algorithm if I am also required to print the shortest path? Will greedy approach help in that? I now officially know I suck at greedy algorithms :(

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