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 X and A, such that solution returns the minimum index of A  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 i , 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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

# 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)

Link to GitHub solution here .
Link to Codility problem here .