Check if two arrays are permutation of each other
  • 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 Answers

< 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;
}


You need to Sign In to post your solution.