### Check if two arrays are permutation of each other array searching permutation    Posted: 7 years ago Updated: 6 years ago Edit answers (1) views (11837)

You are given two integer arrays. How will you check whether they are permutation of each other?

 Posted: 7 years ago Updated: 7 years ago 0 0 Edit < Method 1 : Linearithmic time, no space > Sort the two arrays. Compare each element of both the arrays from beginning to end. If there is no mismatch, return true. Otherwise, false. Sorting time complexity is $$O(nlogn)$$. The comparison costs $$O(n)$$. $$\therefore$$ Overall time complexity = $$O(nlogn)$$. No additional space is needed since we have changed the original array.public boolean checkPermutation(int[] array1, int[] array2){ /* If two arrays have different length - not a permutation*/ if (array1.length !== array2.length) return false; /* Sort 1st array */ Arrays.sort(array1); /* Sort 2nd array */ Arrays.sort(array2); for(int i = 0; i < array1.length; i++){ if(array1[i] !== array2[i]) return false; } return true; } < Method 2 : Linear time, linear space > Assumption : No duplicates Create a Hash Table for all the elements of any one of the arrays. Traverse the other array from beginning to end and search for each element in the Hash Table. If all elements are found in the Hash Table, return true. Otherwise, false. Time complexity = $$O(n)$$ (For creation of hash table and look-up), space complexity = $$O(n)$$.public boolean checkPermutation(int[] array1, int[] array2){ /* If two arrays have different length - not a permutation*/ if (array1.length !== array2.length) return false; /* Create the hash table */ Map myMap = new Hashtable(); /* Iterate through the 1st array and put the element in the hash table */ for(int i = 0; i < array1.length; i++) myMap.put("array1[i]", array1[i]); /* Iterate through the 2nd array and find the element in the hash table */ for(int i = 0; i < array2.length; i++) { boolean isExist = myMap.containsValue(array2[i]); if(isExist == false) return false; } return true; }