Solution to Codility lesson2-exercise2 Permutation Check 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 1,000,000,000 \wedge |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.

Problem:
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. 

Analysis:

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