Sarah M - 1 year ago 88
Java Question

# Frog Cross River - improving used data structures

I was trying to do this exercice from codility:

A small frog wants to get to the other side of a river. The frog is currently located at position 0, and wants to get to position X. Leaves fall from a tree onto the surface of the river.

You are given a non-empty zero-indexed array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in minutes.

The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X.

Write a function:

``````class Solution { public int solution(int X, int[] A); }
``````

that, given a non-empty zero-indexed array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.

If the frog is never able to jump to the other side of the river, the function should return −1.

My solution:

``````public int solution(int X, int[] A) {

int[] vDestT = new int[A.length];
int j = 0;
// find times where X is visited
// sort the array vDestT increasing order
for (int i = 0; i < A.length; i++) {
if (A[i] == X && i > X - 1) {
// put times  corresponding to requested destination X in vDestT in an increasing order
if (j > 0 && i < vDestT[j - 1]) {
int temp = vDestT[j - 1];
vDestT[j - 1] = i;
vDestT[j] = temp;
} else
vDestT[j] = i;
j++;
}
}

int k = 0;
while (k < vDestT.length) {
int remainP = X - 1;
int remainT = vDestT[k] - 1;
// check A[0..X-1]
while (remainT >= remainP) {
if (A[remainT] < X) {
remainP--;
}
if (remainP == 0)
return vDestT[k];
remainT--;
}
if (remainT < remainP) {
k++;
continue;
}

}
return -1;

}
``````

Well, it's the first solution that came to my mind (got 18/100 score) and would like to improve it, so I have some questions:
- By which structure should I replace vDestT?

-What are the conditions I missed(else than
`if(A.length<X) and if (A.length == 1 && X==1)`
)?

EDIT:
I thought that I have to find all times i where A[i] = X, put the "i"s in a sorted array increasing order. Starting with the 1st element from that array which I named vDestT, and see if I can get all the X-1 positions before that time, if not check the second time where A[i] = X. => A very complicated method, I don't know why I was convinced that I should get all times where A[i] = X and sort them in order to find the earliest time.