[LeetCode] Jump Game

This problem has a very concise solution in this link, just 4-lines. The code is rewritten below.

1 class Solution {
2 public:
3     bool canJump(vector<int>& nums) {
4         int i = 0, n = nums.size();
5         for (int r = 0; i < n && i <= r; i++)
6             r = max(r, i + nums[i]);
7         return i == n;
8     }
9 };

The above code can be further optimized by avoiding unnecessary checks. Once we are able to reach the last position, we are already done.

1 class Solution {
2 public:
3     bool canJump(vector<int>& nums) {
4         int i = 0, r = 0, n = nums.size();
5         for (; i < n && i <= r && r < n - 1; i++)
6             r = max(r, i + nums[i]);
7         return r >= n - 1;
8     }
9 };

Or we can rewrite the code a bit longer to make the idea obvious.

 1 class Solution {
 2 public:
 3     bool canJump(int A[], int n) {
 4         int start = 0, end = 0;
 5         while(start <= end && end < n - 1) { 
 6             end = max(end, start + A[start]);
 7             start++;
 8         }
 9         return end >= n - 1;
10     }
11 };