Jun 272015
 

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.
flights101

  8 Responses to “Check if two arrays are permutation of each other”

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

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

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

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

  5. 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

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

  7. 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)

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)