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:

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*/