Check if two arrays are permutations of each other

/ DSA / By
Spread the love
Check if two arrays are permutations of each other

Write a function that, given two identically sized unsorted arrays, returns true if the arrays are permutations of one another and false otherwise.

Examples

Input: arr1[] = {2, 1, 3, 5, 4, 3, 2}
       arr2[] = {3, 2, 2, 4, 5, 3, 1}
Output: Yes
Input: arr1[] = {2, 1, 3, 5,}
       arr2[] = {3, 2, 2, 4}
Output: No

We strongly advise you to try this yourself first by minimizing your browser.
Sorting both arrays and comparing the sorted arrays is a straightforward solution. This solution’s temporal complexity is O(nLogn).

Using Hashing is a better option.

  • For every element in arr1[], create a hash map using array elements as keys and counts as values.
  • Go over arr2[] and look for every element in the Hash Map. Decrease the element’s count in the hash map if it is discovered. Return false if it cannot be located.
  • Return true if every element has been located.

The application of this strategy is seen below.

C++

// A C++ program to find one array is permutation of other array
#include <bits/stdc++.h>
using namespace std;

// Returns true if arr1[] and arr2[] are permutations of each other 
bool arePermutations(int arr1[], int arr2[], int n, int m)
{
	
	// Arrays cannot be permutations of one another unless they are 
	// of the same length
	if(n != m)
	{
		return false;
	}

	// Creates an empty hashMap hM
	unordered_map<int, int> hm;
	
	// Traverse through the first array and add elements to hash map
	for (int i = 0; i < n; i++)
	{
		int x = arr1[i];
		hm[x]++;
	}
	
	// Traverse through second array and check if every element is
	// present in hash map
	for (int i = 0; i < m; i++)
	{
		int x = arr2[i];
	
		// If element is not present in hash map or element
		// is not present less number of times
		if(hm[x] == 0)
		{
			return false;
		}
		hm[x]--;
	}
	return true; 
}

// Driver function to test above function
int main() {
	int arr1[] = {2, 1, 3, 5, 4, 3, 2};
	int arr2[] = {3, 2, 2, 4, 5, 3, 1};
	int n = sizeof(arr1)/sizeof(arr1[0]);
	int m = sizeof(arr2)/sizeof(arr2[0]);
	if (arePermutations(arr1, arr2, n, m))
		cout << "Arrays are permutations of each other" << endl;
	else
		cout << "Arrays are NOT permutations of each other" << endl;
	
	return 0;
}

// This code is contributed by avanitrachhadiya2155

Java

// A Java program to find one array is permutation of other array
import java.util.HashMap;

class Permutations
{
	// Returns true if arr1[] and arr2[] are permutations of each other
	static Boolean arePermutations(int arr1[], int arr2[])
	{
		// Arrays cannot be permutations of one another unless they are 
		// of the same length
		if (arr1.length != arr2.length)
			return false;
	
		// Creates an empty hashMap hM
		HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();

		// Traverse through the first array and add elements to hash map
		for (int i = 0; i < arr1.length; i++)
		{
			int x = arr1[i];
			if (hM.get(x) == null)
				hM.put(x, 1);
			else
			{
				int k = hM.get(x);
				hM.put(x, k+1);
			}
		}

		// Traverse through second array and check if every element is
		// present in hash map
		for (int i = 0; i < arr2.length; i++)
		{
			int x = arr2[i];

			// If element is not present in hash map or element
			// is not present less number of times
			if (hM.get(x) == null || hM.get(x) == 0)
				return false;

			int k = hM.get(x);
			hM.put(x, k-1);
		}
		return true;
	}

	// Driver function to test above function
	public static void main(String arg[])
	{
		int arr1[] = {2, 1, 3, 5, 4, 3, 2};
		int arr2[] = {3, 2, 2, 4, 5, 3, 1};
		if (arePermutations(arr1, arr2))
			System.out.println("Arrays are permutations of each other");
		else
			System.out.println("Arrays are NOT permutations of each other");
	}
}

Python3

# Python3 program to find one 
# array is permutation of other array
from collections import defaultdict

# Returns true if arr1[] and 
# arr2[] are permutations of 
# each other
def arePermutations(arr1, arr2):
	# Arrays cannot be permutations of one another
	# unless they are of the same length
	if (len(arr1) != len(arr2)):
		return False
	
	# Creates an empty hashMap hM
	hM = defaultdict (int)

	# Traverse through the first 
	# array and add elements to 
	# hash map
	for i in range (len(arr1)):
		
		x = arr1[i]
		hM[x] += 1
		
	# Traverse through second array 
	# and check if every element is
	# present in hash map
	for i in range (len(arr2)):
		x = arr2[i]

		# If element is not present 
		# in hash map or element
		# is not present less number 
		# of times
		if x not in hM or hM[x] == 0:
			return False

		hM[x] -= 1
		
	return True

# Driver code
if __name__ == "__main__":

	arr1 = [2, 1, 3, 5, 4, 3, 2]
	arr2 = [3, 2, 2, 4, 5, 3, 1]
	if (arePermutations(arr1, arr2)):
		print("Arrays are permutations of each other")
	else:
		print("Arrays are NOT permutations of each other")
		
# This code is contributed by Chitranayal

C#

// C# program to find one array
// is permutation of other array
using System;
using System.Collections.Generic;

public class Permutations {
	// Returns true if arr1[] and arr2[]
	// are permutations of each other
	static Boolean arePermutations(int[] arr1, int[] arr2)
	{
		// Arrays cannot be permutations of one another if
		// they are not the same length
		if (arr1.Length != arr2.Length)
			return false;

		// Creates an empty hashMap hM
		Dictionary<int, int> hM = new Dictionary<int, int>();

		// Traverse through the first array
		// and add elements to hash map
		for (int i = 0; i < arr1.Length; i++) {
			int x = arr1[i];
			if (!hM.ContainsKey(x))
				hM.Add(x, 1);
			else {
				int k = hM[x];
				hM.Remove(x);
				hM.Add(x, k + 1);
			}
		}

		// Traverse through second array and check if every
		// element is present in hash map (and the same
		// number of times)
		for (int i = 0; i < arr2.Length; i++) {
			int x = arr2[i];

			// If element is not present in hash map or
			// element is not present the same number of
			// times
			if (!hM.ContainsKey(x))
				return false; // Not present in the hash map

			int k = hM[x];
			if (k == 0)
				return false; // Not present the same number
							// of times
			hM.Remove(x);
			hM.Add(x, k - 1);
		}
		return true;
	}

	// Driver code
	public static void Main()
	{
		int[] arr1 = { 2, 1, 3, 5, 4, 3, 2 };
		int[] arr2 = { 3, 2, 2, 4, 5, 3, 1 };
		if (arePermutations(arr1, arr2))
			Console.WriteLine("Arrays are permutations of each other");
		else
			Console.WriteLine("Arrays are NOT permutations of each other");
	}
}

/* This code contributed by PrinciRaj1992 */

JavaScript

<script>

// A Javascript program to find one array 
/// is permutation of other array
	
	// Returns true if arr1[] and arr2[] 
	// are permutations of each other
	function arePermutations(arr1,arr2)
	{
		// Arrays cannot be permutations of 
		// one another unless they are
		// of the same length
		if (arr1.length != arr2.length)
			return false;
		
		// Creates an empty hashMap hM
		let hM = new Map();

		// Traverse through the first array
		// and add elements to hash map
		for (let i = 0; i < arr1.length; i++)
		{
			let x = arr1[i];
			if (!hM.has(x))
				hM.set(x, 1);
			else
			{
				let k = hM[x];
				hM.set(x, k+1);
			}
		}

		// Traverse through second array and 
		// check if every element is
		// present in hash map
		for (let i = 0; i < arr2.length; i++)
		{
			let x = arr2[i];

			// If element is not present in 
			// hash map or element
			// is not present less number of times
			if (!hM.has(x) || hM[x] == 0)
				return false;

			let k = hM[x];
			hM.set(x, k-1);
		}
		return true;
	}
	
	// Driver function to test above function
	let arr1=[2, 1, 3, 5, 4, 3, 2];
	let arr2=[3, 2, 2, 4, 5, 3, 1];
	if (arePermutations(arr1, arr2))
		document.write(
		"Arrays are permutations of each other"
		);
	else
		document.write(
		"Arrays are NOT permutations of each other"
		);
	
	// This code is contributed by rag2127
	
</script>

Output

Arrays are permutations of each other