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\$

2 Answers 2

Reset to default
7
\$\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\$
2
  • 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\$ Commented Mar 5, 2019 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\$ Commented Mar 5, 2019 at 16:10
4
\$\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\$
4
  • 1
    \$\begingroup\$ I think your final conditional is not even needed and you can just return 1 after the loop exits. \$\endgroup\$ Commented Mar 5, 2019 at 13:02
  • \$\begingroup\$ @OhMyGoodness Yes. good point. \$\endgroup\$ Commented Mar 5, 2019 at 14:40
  • \$\begingroup\$ if (len > 1e5) { return 0 } is redundant, given the assumptions \$\endgroup\$ Commented Mar 9, 2019 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\$ Commented Mar 9, 2019 at 1:55

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.