The Perm Check Challenge defines a permutation as a sequence containing each element from 1 to N once, and only once. So the order does not matter.
I devised an algorithm which solves the problem with O(N) or O(N * log(N)) complexity.
I look first for the maximum value of the array, N. Then, if the length of the array is different than N, I return 0 – this is not a permutation.
Moving on, then I counted the occurrences of each element in the array in a new array, B. If there is no value 0 in the array, then A was a permutation, otherwise, it was not.
Here is the code:
function solution(A) {
// write your code in JavaScript (Node.js 8.9.4)
let max = 0
for (let i = 0; i < A.length; i++){
if (A[i] > max) max = A[i]
}
if (A.length !== max) return 0
let Indexes = Array(max).fill(0)
for (let i = 0; i < A.length; i++){
Indexes[A[i]-1]++
}
result = Indexes.indexOf(0)
if (result === -1) {
return 1
} else {
return 0
}
}
And here is the report.
Tell me in the comments if you used a more optimized version!