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


  • 50

    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;
    }

  • 14
    M

    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;
    	}
    }

  • 0
    D

    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.


  • 0
    D
    This post is deleted!

  • 1
    W

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


  • 0

    Thanks for sharing!


  • 0

    @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;
        }
    

  • 0
    C

    @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.


  • 0
    D
    This post is deleted!

  • 0
    H

    How to deal with [0, 1] ?


Log in to reply
 

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