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