# Codility - Frog River One

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

Definitions:
$\mathbf{A} = \{x \in \mathbb{N}\ | 1 \leq x \leq X\}\mathbf{A}\, is\, a\, multiset.$
$\{N, X \in \mathbb{N}\ |\ 1 \leq N, X \leq 100,000\}$

Problem:
Define a function solution with input and A, such that solution returns the minimum index of  where all elements of the sequence $\{1,..,X\}$, 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 , and a variable to count the first appearance.

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.

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: Frog River One Python # 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 12345678910111213141516171819202122 # 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)