Solution to Codility lesson2-exercise1 Frog River One problem, link to Codility problem and complete solution at the end of the post.

**Definitions:
**

** Problem:**Define a function

*solution*with input

*X*and

*A*, such that

*solution*returns the minimum index of

*A*where all elements of the sequence

, has appeared, if there isn’t such index, the function should return *-1*.

- Expected worst-case time complexity is
*O(N)*; - Expected worst-case space complexity is
*O(X)*, beyond input storage (not counting the storage required for input arguments).

**Elements of input arrays can be modified.**** **

### Analysis:

The strategy here is to count the first appearance of every element of the sequence, to accomplish that we’ll use an array with size *(X + 1)*, that will mark at index *i* the appearance of a leaf at position *i *, and a variable to count the first appearance.

7 8 9 |
# Counts the appearance of leaves at every position from the 1 to X count = [0] * (X + 1) total = 0 |

Then we visit every element of *A, *until we reach a total of *X*, meaning that we have a leaf at every position from *1* to *X.*

11 12 13 14 15 16 17 18 19 20 |
for k in xrange(N): # If it's the first time that the leaf appears at position A[k] adds one to total if count[A[k]] == 0: total += 1 # If there is a leaf in every position from 1 to X, returns the current array index if total == X: return k # Marks the position A[k] with a leaf count[A[k]] = 1 |

The worst case scenario here, it’ll be if we have to visit every element of *A*, to find our solution, giving a total time complexity of O(N).

For the space complexity, we’ll have *O(X)*, because of the *count* array, since its size depends on the value of X.

**Complete Solution:**

1234567891011121314151617181920212223
# Name FrogRiverOne# Link https://codility.com/demo/take-sample-test/frog_river_one/ def solution(X, A): N = len(A) # Counts the appearance of leaves at every position from the 1 to X count = [0] * (X + 1) total = 0 for k in xrange(N): # If it's the first time that the leaf appears at position A[k] adds one to total if count[A[k]] == 0: total += 1 # If there is a leaf in every position from 1 to X, returns the current array index if total == X: return k # Marks the position A[k] with a leaf count[A[k]] = 1 return -1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
# Name FrogRiverOne # Link https://codility.com/demo/take-sample-test/frog_river_one/ def solution(X, A): N = len(A) # Counts the appearance of leaves at every position from the 1 to X count = [0] * (X + 1) total = 0 for k in xrange(N): # If it's the first time that the leaf appears at position A[k] adds one to total if count[A[k]] == 0: total += 1 # If there is a leaf in every position from 1 to X, returns the current array index if total == X: return k # Marks the position A[k] with a leaf count[A[k]] = 1 return -1 |

*Time Complexity O(N)*

*Space Complexity O(X)*

## One thought on “Codility – Frog River One”