Could you help me with this Codility Array Problem?-CodePudding

A non-empty array A consisting of N integers is given. Each element of the array can be treated as a relative pointer to another element in the array: if A[K] = M then element A[K] points to element A[K M]. The array defines a sequence of jumps of a pawn as follows:

initially, the pawn is located at element A[0];
on each jump the pawn moves from its current element to the destination element pointed to by the current element; i.e. if the pawn stands on element A[K] then it jumps to the element pointed to by A[K];
the pawn may jump forever or may jump out of the array.

For example, consider the following array A.

A[0] = 2 ; A1 = 3 ; A[2] = -1 ; A[3] = 1 ; A[4] = 3

This array defines the following sequence of jumps of the pawn:

initially, the pawn is located at element A[0];
on the first jump, the pawn moves from A[0] to A[2] because 0 A[0] = 2;
on the second jump, the pawn moves from A[2] to A1 because 2 A[2] = 1;
on the third jump, the pawn moves from A1 to A[4] because 1 A1 = 4;
on the fourth jump, the pawn jumps out of the array.

Write a function: that, given a non-empty array A consisting of N integers, returns the number of jumps after which the pawn will be out of the array. The function should return −1 if the pawn will never jump out of the array.

Given array A such that: A[0] = 1 ; A1 = 1 ; A[2] = -1 ; A[3] = 1

the function should return −1.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];
each element of array A is an integer within the range [−1,000,000..1,000,000].

I've already have a solution but i didn't pass the performance test :

int sol(int[] A) {
    int jump = 0;
    int index = 0;
    List<Integer> oldIndex = new ArrayList<Integer>();
    while (index < A.length) {
        if (index < 0) {
            return jump;
        }
        oldIndex.add(index);
        index = A[index]   index;
        if (oldIndex.contains(index)) {
            return -1;
        }
        jump  ;
    }
    return jump;
}

Can anyone help me find anyway to improve performance or any ideas for a better solution.Thank you .

CodePudding user response：

Your approach is right, but instant list reallocation can make program slower.

It is claimed that value range is limited, so you can just put off-range constant (like 2000000) into visited cells as sentinel and stop when you meet such value.

Something like this (not checked):

int sol(int[] A) {
    int jump = 0;
    int index = 0;
    int old = 0;
    int alen = A.length;
    while (index < alen && index >= 0) {
        old = index;
        index = A[index]   index;
        if (A[index] >= 2000000)  {
            return -1;
        }
        A[old] = 2000000;
        jump  ;
    }
    return jump;
}