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.

\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\}

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. 


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:

Time Complexity O(N)
Space Complexity O(X)

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

One thought on “Codility - Frog River One

/*Comment here*/