LeetCode: Jump Game I && 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.

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.

Solution

At first glance, the problem can be solved with recursion or BFS. However, both solutions got the TLE error. Apparently, the intended solution should have less time complexity.

Key point: use maxCover to indicate the maximum index that current index can reach. Update the value of maxCover correspondingly.

For Jump Game II. Tried BFS first, got TLE error. Then figured out the right answer based on the solution of Jump Game I. Key point: use a tempoary variable tempCover to get the largest A[i]+i  from all the indices within current maxCover.