# Jump Game

## Simulating

```
0 1 2 3 4
A[2,3,1,1,4]
```

from A[0], can jump to every pos between `0`

and `0 + A[0]`

from A[1], can jump to every pos between `1`

and `1 + A[1]`

so..
from A[i], can jump to every pos between `i`

and `i + A[i]`

C[i] is a paper that help us to remember if we can jump to pos `i`

```
0 1 2 3 4
A[2,3,1,1,4]
C[0,0,0,0,0]
```

```
for A[0] C[0 .. 0 + A[0]] = 1
for A[1] C[1 .. 1 + A[1]] = 1
for A[i] C[i .. i + A[i]] = 1
```

thus, code should be like below

```
C[0] = 1
foreach i in A
if C[i] == 1 then
C[i .. i + A[i]] = 1
return C[last i of A]
```

## Array C is not needed

when we set
```
C[i .. i + A[i]] = 1
```

is equals

```
foreach i in A
C[0 .. max of i + A[i]] = 1
```

is equals

```
maxjump = 0
foreach i in A
maxjump = max(maxjump, i + A[i])
```

so `C[i]`

can be replaced by `i < maxjump`

Removing C would save memory and the time used for setting them to 1

### Source code *Read on Github*

```
1 public class Solution {
2
3
4
5 public boolean canJump(int[] A) {
6 // Note: The Solution object is instantiated only once and is reused by each test case.
7 if(A.length == 0) return false;
8
9
10 int maxjump = 0;
11
12 for(int i = 0; i < A.length; i++){
13 if(i <= maxjump){
14 if(i + A[i] < A.length - 1){
15 maxjump = Math.max(maxjump, i + A[i]);
16 }else{
17 return true;
18 }
19 } else {
20 return false;
21 }
22 }
23
24 return false;
25 }
26 }
```