Perl compare two arrays

Two arrays differences

Given two integer arrays A and B of the same size each having no duplicate values. Write an equality function that returns true if A and B are equivalent. The arrays are equivalent if they contain the same content regardless of order. The function should return false if the arrays are not equivalent. Your algorithm must run in linear time O(N) where N is the size of the array.

Solution

The brute force method to solve this problem is to loop through the elements of the first array comparing the current element to all elements of the second array. If the current element can not be found in the second array then we return false otherwise we continue looping. This method does not run in linear time because it involves two nested loops. The outer loop executes N times and the inner loop can potentially execute up to N times so the algorithm complexity in the worst case scenario is O(N2) In order to solve this problem in linear time we need to remove the inner loop using a data structure that is lookup efficient. Hash table is a good candidate for efficient lookup. We populate the hash table with the elements of the first array then loop through the second array and check if the current element is in the hash. If the element is not in the hash we return false immediately otherwise we continue looping.

Example code

Here is a suggested solution in Perl

Thanks for reading. If you have questions or comments, please use the comments section below.