Sarah M Sarah M - 8 months ago 34
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.

m69 m69
Answer Source

There's no need to store all the times per location and then sort them, because you're only interested in the first one. Also, the input is chronological, so you may not need to check it all the way to the end.

  • Create a data structure capable of storing X boolean values, and set them to false.
  • Create a counter variable and set it to zero.
  • Iterate over A, and for each time i, if the boolean for location A[i] is false, set it to true and increment the counter.
  • As soon as the counter equals X, all locations are true, and time i is your answer.
  • If at the end of A, the counter is less than X, some locations remain empty.

This way, you only iterate over the input once, and the answer is found in X to N steps, i.e. linear time complexity.