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);
}

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;
}