Problem

I have just attended a code test of some code testing site, and I think one question seems easy but I didn’t get a high correctness, so if anyone can review this code snippet, I would appreciate it.

In summary:

Given an array `A`

, with dimension `N`

, 1<=`N`

<=100000, `A[N]`

within range of [-100000, 100000]. At first there is a pointer at position `K`

(in the beginning `K=0`

), and `M=A[K]`

, and we say the pointer will jump to position `A[K+M]`

, and call this a “jump of a pawn`. If at any moment, the pointer jumps out of the array, we must return the steps of jumps it takes. If it will never jump out, return -1.

```
class Solution {
public Solution() {}
public int solution(int[] A) {
int next = A[0] + 0;
int N = A.length;
Map<Integer, Integer> count = new HashMap<Integer, Integer>();
for (int i=0; i<N; i++) {
count.put(i, 0);
}
count.put(0, 1); //already pass position 0 once
int times = 0;
while (next < N && next >= 0) { /* next index can be negative!!!!! Error!!!! */
times ++;
next = A[next] + next;
System.out.println("Now the next index is: " + next);
if (next >= N || next < 0) { /* next index can be negative!!!!! Error!!!! */
System.out.println("Now jump out. ");
return times+1;
}
count.put(next, count.get(next) + 1);
if (count.get(next) > 1) {
System.out.println("Repeated index " + next + ", will not jump out");
return -1;
} else {
continue;
}
}
return times + 1; //edited
}
}
```

EDIT:

With this version I know that it is higher than 57% (original result of the quiz), but I cannot say it is 100% because I don’t have all the test cases used in evaluation.

Solution

```
Map<Integer, Integer> count = new HashMap<Integer, Integer>();
for (int i=0; i<N; i++) {
count.put(i, 0);
}
```

This will consume memory linearly in the size of the array. I don’t know what constraints you have on memory, but this doesn’t seem like the best use of it.

- If your average path through the array is short and memory is not at a premium, use a HashMap but do not pre-populate it with zero. That way you’re actually allocating memory in proportion to the length of the path rather than the length of the array.
- If your typical path through the array visits a significant proportion of the cells in the array, and memory is not at a premium, just use a Boolean array to store whether a cell has been visited. Arrays will be cheaper than HashMaps.
- If you cannot really afford the memory to store the visited cells, have a look at the “hare and tortoise” algorithm for cycle finding.

```
/* next index can be negative!!!!! Error!!!! */
```

This comment appears twice, but it seems unhelpfully alarming to me. You’re guarding the next index value to check whether it is within the array; you’re handling both negative and excessive index values the same. That isn’t an error.

```
System.out.println("Now the next index is: " + next);
```

Although useful for debugging, a function like this should not continually print out its progress. That just slows down running and annoys the person using it. (More generally, a function like this should probably avoid having any side effects.)

```
else {
continue;
}
```

This is redundant. The loop would continue anyway.

```
int next = A[0] + 0;
```

As JSI mentioned in a comment, this is a bit confusing. It would be better to use the loop logic for all cases if you possibly can, rather than coding special cases outside. You could just start with `int next = 0`

(as if you’re just about to jump into the array). This would let you simplify things, like having `times`

be the actual number of jumps and therefore letting the first return clause just be `return times;`

As written I do think the algorithm is wrong. If the first jump takes you out of the array, it will return 0 when it should return 1.

The edge case you do need to handle expressly is the case where the size of the input array is 0.