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

Definitions:  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 , 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)