4
\$\begingroup\$

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;
    }
}
\$\endgroup\$
5
\$\begingroup\$

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);
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Mike Brant Mar 5 at 3:27
  • \$\begingroup\$ @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. \$\endgroup\$ – Oh My Goodness Mar 5 at 16:10
1
\$\begingroup\$

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;
}         
\$\endgroup\$
  • 1
    \$\begingroup\$ I think your final conditional is not even needed and you can just return 1 after the loop exits. \$\endgroup\$ – Oh My Goodness Mar 5 at 13:02
  • \$\begingroup\$ @OhMyGoodness Yes. good point. \$\endgroup\$ – Blindman67 Mar 5 at 14:40
  • \$\begingroup\$ if (len > 1e5) { return 0 } is redundant, given the assumptions \$\endgroup\$ – André Werlang Mar 9 at 0:11
  • \$\begingroup\$ @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. \$\endgroup\$ – Blindman67 Mar 9 at 1:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.