Check if two arrays are permutation of each other

Given two arrays of integers, write a code to check if one is permutation (arranging the same numbers differently) of elements present in the other. For example, the below two arrays are permutations of each other:

    int a[5] = {1, 2, 3, 4, 5};
    int b[5] = {2, 1, 4, 5, 3};

Solution-1: Use multiplication and addition

• Multiply all elements of first array, call it mul1.
• Multiple all elements of second array, call it mul2.
• Add all elements of first array, call it sum1.
• Add all elements of second array, call it sum2.

If mul1 is equal to mul2 and sum1 is equal to sum2, then the two arrays are permutations of each other else, they are not.

Code:

bool checkPermutation1(int* a, int m, int* b, int n)
{
    // If two are not of same size then not permutation.
    if(m != n){ return false; }
    if(a==NULL && b==NULL){ return true; }
    int mul1 = 1;
    int mul2 = 1;
    int sum1 = 0;
    int sum2 = 0;
    for(int i=0; i<m; i++){
        mul1 *= a[i];
        mul2 *= b[i];
        sum1 += a[i];
        sum2 += b[i];
    }
    if(mul1 == mul2 && sum1 == sum2)
        return true;
    else
        return false;
}

But multiplication or addition may result in overflow (or underflow) of integers if numbers are large.
Solution-2: Using Sorting

If two arrays are permutations of each other then the sorted order of these two arrays will be exactly same:

Sort both the arrays, if after sorting the two arrays are exactly same, then they are permutations of each other, else not:

bool checkPermutation2(int* a, int m, int* b, int n)
{
    // If two are not of same size then not permutation.
    if(m != n){ return false; }
    if(a==NULL && b==NULL){ return true; }
    quickSort(a, m);
    quickSort(a, n);
    for(int i=0; i<m; i++){
        if(a[i] != b[j]){
            return false;
        }
    }
    return true;
}

Solution-3: Using Hashing

First create the harsh using the first array, then iterate the second array, and for each element of the array, remove it from the hash. If after the second array traversal, the hash becomes empty it means that both are permutations of each other.

Time Complexities

• Solution-1 takes O(n) time and constant memory.
• Solution-2 takes O(n.lg(n)) times and constant memory.
• Solution-3 takes O(n) time and O(n) memory.