Leetcode Jump Game I & II (Java)

Tags: ,

Jump Game I 

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

 
Analysis:
We maintain the max step can be reached so far.  If an index i is larger than the current max step that can be reached, it returns false.
 

Java Solution:

 
 

Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

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

Analysis

We keep three pointers,

i: the index of current visiting item,

maxSoFar: the max index that can be reached since last change of step

curMax: the max index that can be reached from the index that is smaller than maxSoFar.

For each i <= maxSoFar, we update curMax = max(curMax, i + num[i]),

Then we update maxSoFar by curMax and increase cnt. Since it is assumed that the array can always be reachable, curMax will always be larger than maxSoFar. 

Once maxSoFar > nums.length, return cnt. 

Java Solution