The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

Problem

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:

    int solution(int 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].

Note:

For the permutation above, N = 4. This means that all the numbers in the array can be put in order as follows: 1, 2, 3, 4 (four numbers). The lesson for this problem is Counting Elements. The candidate should expect that the solution to this problem, needs a count array (frequency-of-occurrences-array). With this, the highest possible value in a given array should be N. For a permutation, the number of occurrences of each value in the given array has to be 1 (verified in the count array).

In the non-permutation array in the question, it is true that 2 is missing, but since N, the number of elements is 3, it means that 4 is bigger than N = 3, and that is an accompanied error. Some other number, even bigger than 4 could have been in the place of 4. In that case, more than one number would appear to be missing. The integers for this array are supposed to be: 1, 2, 3, in any order; so only 2 is missing.

Another possibility of error is that, an integer less than N can occur more than once, and/or with some numbers missing, as in the following list:

    1, 1, 1, 4

Here, 1 has occurred three times with 2 and 3 missing. The highest expected number, 4 is still there. The numbers are supposed to be 1, 2, 3, 4.

Strategy

The count tables for the first two arrays above are as follows:

Remember that index 0 and its value of 0 is in the two tables, for convenience (they are not used). Note that in the non-permutation table, the value (number of occurrences) of the index 2, is 0; meaning 2 is missing.

So, to know if an array is not a permutation, check if there is an integer which is higher than N (4 is higher than 3 for the second example above); check if any integer between 1 and N (inclusive) is missing; and check if any integer between 1 and N (inclusive) occurs more than once.

In order to know if any integer is missing or if any integer occurs more than once, a count array is needed. Both of these requirements are checked, whether all the values in the count array are 1 (if a given value is missing, then its count is 0; if a given value occurs more than once, then its count is not 1, and is greater than 1).

Checking if an integer is greater than N should be done as the given array is scanned to produce the count array. The given array is scanned in N time to produce the count array of m + 1 cells (including index 0). Another complete N scanning should not waste the time complexity just to know if there is a number in the list that is greater than N, in N time.

The given array is scanned in N time to produce the count array, and then the count array is scanned in M time, to make sure all the values are 1.

O(N+M) Time Solution

The program is (read through the code and comments):

#include <stdio.h>

int solution(int A[], int N) {
    int count[N+1];    //N is M here
    for (int i=0; i < N+1; i++)
        count[i] = 0;    //initializing count array

    for (int i=0; i < N; i++) {
        if (A[i] > N)
            return 0;    //for false
        count[A[i]]++;  //i.e. count[A[i]] = count[A[i]] + 1;
    }

    for (int i=1; i < N+1; i++) {
        if (count[i] != 1)  //count[i] is 0 or above 1
            return 0;   //for false
    }

    return 1;    //for true, if no wrong condition detected
}
  
int main(int argc, char **argv) 
{
    int A1[] = {4, 1, 3, 2};
    int N1 = sizeof(A1) / sizeof(A1[0]);    //length of given array
    int ret1 = solution(A1, N1);
    printf("%i\n", ret1);
    
    int A2[] = {4, 1, 3};
    int N2 = sizeof(A2) / sizeof(A2[0]);    //length of given array
    int ret2 = solution(A2, N2);
    printf("%i\n", ret2);
    
    return 0; 
}

The time complexity for the called function is O(N+M), with N for scanning the given array to produce the content of the count array, and M for scanning the count array to check if any element (value) is not 1. The O(M) time to create the count array, initializing everything (element) to zero, is ignored here. The space complexity is O(N+M), for the two arrays.

Thanks for reading.