Codility - Permutation Check

Solution to Codility lesson2-exercise2 Permutation Check problem, link to Codility problem and complete solution at the end of the post.

\mathbf{A} = \{x \in \mathbb{N}\ | 1 \leq x \leq 1,000,000,000 \land |A| = N \},\mathbf{A}\, is\, a\, multiset.
\{N \in \mathbb{N}\ |\ 1 \leq N \leq 100,000\}
Codility Permutation definition: A permutation of size N is a sequence containing each element from 1 to N once, and only once.

Define a function solution with input A, such that solution returns 1 if A is a permutation and if it is not.

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

Elements of input arrays can be modified. 


This one is very similar to the Frog River One, we'll also count the first appearance of every element of the sequence \{1,..,N\}, but if we find a element of  that is greater than or a duplicate element this means that A can't be a permutation by the Codility definition.

If we visited all elements of and didn't find any repeated element or any greater than N, this means that we have a permutation, and we can return 1.
Since we have to visit all elements of A to guarantee that A is a permutation the total time complexity is O(N).
For the space complexity, we'll have O(N), because of  the count array, since its size depends on the value of N.

Complete Solution:

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

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

/*Comment here*/