# Linear and simple solution in C++

• I just iterate and update the maximal index that I can reach

``````bool canJump(int A[], int n) {
int i = 0;
for (int reach = 0; i < n && i <= reach; ++i)
reach = max(i + A[i], reach);
return i == n;
}``````

• Cool!!!!, thanks for share， I run it in my head, and finally get the idea.
I just wondering how do you get this solution.

Greedy. the tag of the problem. great.

• ``````class Solution:
# @param A, a list of integers
# @return a boolean
def canJump(self, A):
if not A:
return False

maxjump=0
for i in range(len(A)):
maxjump=max(maxjump-1,A[i])
if maxjump==0:
break

return i==len(A)-1
``````

for python

• This post is deleted!

• Maybe for some special case ,no need to check all elements. A little change to you shearing code.Thx @alexander7

``````class Solution {
public:
bool canJump(int A[], int n) {
int i = 0, maxreach = 0;
for (; i < n && i <= maxreach && maxreach < n - 1; ++i)
maxreach = max(maxreach,i+A[i]);
return maxreach>=n-1;
}
};``````

• what does maxjump-1 mean?

• This is soooooooooooooooo brilliant!

• ``````public boolean canJump(int[] nums) {
int dis = 0;
for (int i = 0; i <= dis; i++) {
dis = Math.max(dis, i + nums[i]);
if (dis >= nums.length-1) {
return true;
}
}
return false;
}
``````

No need to scan whole array when already know we can reach the end.

• I think your code may be improved to stop early?

See below mine:

``````class Solution {
public:
bool canJump(vector<int>& nums) {
int n=nums.size(),reachablesofar=0;

for(int i=0;i<n;i++){
if(reachablesofar<i) return false;
reachablesofar=max(reachablesofar, i+nums[i]);
if(reachablesofar>=n-1) return true;
}
}
};``````

• check condition (i <= reach)，it's already contain early stop condition..

• awesoooooooooooome

• brilliant solution

• @alexander7 you are great!

• same idea different implementation.

``````class Solution {
public:
bool canJump(vector<int>& nums) {
int far = 0;
for(int i=0; i<=far && i<nums.size(); ++i){
far = std::max(far, i + nums[i]);
}
return (far >= nums.size()-1) ;
}
};
``````

• such a brilliant solution indeed

• ``````public class Solution {
public boolean canJump(int[] nums) {
return canJump(nums, nums.length);
}

private boolean canJump(int[] nums, int n) {
int i = 0;
// i <= reach, the furthest "start point" that I can reach
// start point + nums[i] >= n, win!
// start point + nums[i] < n, lose!
// so greedy
for (int reach = 0; i < n && i <= reach; ++i)
reach = Math.max(i + nums[i], reach);
return i == n;
}
}
``````

• This post is deleted!

• @alexander7 My mind constraint by the classical game monopoly, but walk one by one step and remember how far I can reach is the key of this problem,thanks for your brilliant solution.

• @alexander7
bool canJump(vector<int>& nums) {
int n = nums.size() - 1, reach = 0;
for(int pos = 0; pos <= reach && reach < n; reach = max(nums[pos] + pos++, reach));
return reach >= n;
}
Base on the problem and your solution,I optimized the code,this seems understandable and earlier stop,but I don't know why almost java's solutions are faster than cpp's.

• @alexander7 so elegant! Thanks for share!

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