Count all left nodes in a Binary tree
June 24, 2015
Fastest horse Interview question
June 28, 2015

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.

10 Comments

  1. shakul says:

    Good Article Kamal!
    Another way to solve this –
    1. create XOR of elements of first set. Let the XOR value is S.
    2. read element of second set one by one and XOR with S i.e. S=S XOR element of second array.
    3. if set 1 is same as set 2 , S will become zero otherwise not.
    complexity O(n)

  2. shakul says:

    Yeah! right if the array has duplicate elements than it will not work. I thought array has unique elements i.e. set not dups.

  3. Parth Sharma says:

    Solution 2 will not work if a entry is 0 for ex 0,1,2,4 on multiplication give 0 and on adding will give 7 and if we have other array as 0,2,2,3 sum is 7 and product is also 0

  4. Kamal Rawat says:

    you are right… Just curious, can you think of any example where the product is not zero?

  5. Kamal Rawat multiplication can case statck overflow or multiplication can results in very large no out of range of the variable

  6. Kamal Rawat says:

    Mehboob Elahi Thanks for pointing it out.. updated the post.

  7. Martin says:

    Solution-1 works only if numbers in the array are unique. It returns true for {0, 1, 1} and {0, 0, 2}.

  8. Sam says:

    Comparing the sum and products of the elements does not work. Suppose a = [1, 9, 10] and b = [2, 3, 15].
    PRODUCT [1, 9, 10] == 90
    PRODUCT [2, 3, 15] == 90
    SUM[2, 3, 15] == 20
    SUM [1, 9, 10] == 20
    [1, 9, 10] is NOT a permutation of [2, 3, 15]

  9. Leia says:

    As a variation of solution-1:
    Can sum of values and sum of squares be a good way of comparing instead of comparing the products and sums?
    sum_of_squares1 = sum_of_squares2
    AND
    sum1 = sum2

Leave a Reply to Anonymous Cancel reply

Your email address will not be published. Required fields are marked *