# Interview Questions

# Check if two arrays are permutation of each other

- June 27, 2015
- Posted by: Kamal Rawat
- Category: Algorithms

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.

**pinkdiamonds.nl**

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

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]

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

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

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

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

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

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

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)

Thanks for the solution.. But, this will not work.. consider two arrays: {1, 1, 3} and {2, 2, 3}. The XOR of these two arrays will be zero