PermCheck Codility

Question

The following code gets 100% on the PermCheck task on Codility. It should be O(N).

The question is:

A non-empty array A consisting of N integers is given.

A permutation is a sequence containing each element from 1 to N once, and only once.

For example, array A such that:

A[0] = 4
A[1] = 1
A[2] = 3
A[3] = 2

is a permutation, but array A such that:

A[0] = 4
A[1] = 1
A[2] = 3

is not a permutation, because value 2 is missing.

The goal is to check whether array A is a permutation.

Write a function:

function solution(A);

that, given an array A, returns 1 if array A is a permutation and 0 if it is not.

For example, given array A such that:

A[0] = 4
A[1] = 1
A[2] = 3
A[3] = 2

the function should return 1.

Given array A such that:

A[0] = 4
A[1] = 1
A[2] = 3

the function should return 0.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [1..1,000,000,000].

Let me know if you think it can be improved, but I think it is pretty good. ;)

function solution(A) {
 let m = A.length;
 let sumA = A.reduce((partial_sum, a) => partial_sum + a);
 let B = Array.apply(null, Array(m)).map(function () {});
 var sum_indices = 0;
 for (var i = 0; i < m; i++) {
 B[A[i] - 1] = true;
 sum_indices += i + 1;
 }
 if (sum_indices == sumA && B.indexOf(undefined) == -1) {
 return 1;
 } else {
 return 0;
 }
}

Answer 1

Summing the arrays is not necessary. You only need to check that the input's maximum and length are equal, and that it's free of duplicates.

This approach scores 100% as well. It saves a couple of array traversals and exits earlier when a duplicate exists.

function solution(A) {
 var max = 0,
 seen = Array( A.length );
 for (var i of A) {
 if (i>max) max=i;
 if (seen[i]) return 0;
 seen[i]=true;
 }
 return +(max == A.length);
}

• Mike Brant: Good solution though I would consider a map or set instead of array for your seen variable, as intent would probably be a little clearer.
• Oh My Goodness: @MikeBrant I tried it before posting, but arrays of integers (or booleans) are very hard to beat, performance-wise. Using a set was about 4x slower. That said, it does make the code tidier. See Blindman67's solution for a good example.

Answer 2

You can use a Set to reduce the mean complexity.

There are also several opportunities to exit the function early.

• When a duplicate is found
• When a value is found greater than the array length

Thus we get...

function solution(A) {
 const found = new Set();
 for (const num of A) {
 if (found.has(num) || num > A.length) { return 0 }
 found.add(num);
 }
 return 1;
} 

• Oh My Goodness: I think your final conditional is not even needed and you can just return 1 after the loop exits.
• Blindman67: @OhMyGoodness Yes. good point.
• André Werlang: if (len > 1e5) { return 0 } is redundant, given the assumptions
• Blindman67: @AndréWerlang Ah yes I see N is the max array length, not the max valid sequence size. No point holding length in len so almost nothing left of the function.