Check whether given a pair of arrays are permutation of each other

Question

Does this implementation guarantee execution of \$O(n)\$ time? What is the additional space utilization for this implementation by excluding the original array size? Is it \$O(1)\$?

#include<iostream>
#include<set>
#include<algorithm>


bool ArraysPermute(int  array1[],int size1, int  array2[], int size2)
{       
       if( size1  != size2)           
           return false;
       else
       {        
           std::set<int> first_set(array1, array1+size1);
           std::set<int> second_set(array2, array2+size2);

           std::pair<std::set<int>::iterator,std::set<int>::iterator> myPair=std::mismatch(first_set.begin(),first_set.end(),second_set.begin());

           if( *myPair.first != *myPair.second)

                return false;
            else
                return true;
       }
}


int main()
{     
    int array1[] ={1,2,3,5};
    int array2[]={1,2,4,3};

    if(ArraysPermute(array1,sizeof(array1)/sizeof(int), array2, sizeof(array2)/sizeof(int)))
        std::cout<< " Arrays are permutation of each other\n"; 
    else
        std::cout<< " Arrays are not permutation of each other\n";

    return 0;
}

Answer 1

Complexity

You suggest that the performance is \$O(n)\$, but it is not. It is \$O(n \log{n})\$ because the set constructor is a binary-tree building algorithm that has an additional log(n) operations for each value.

Style

While your code is all neat, and well laid out, the variable names are good, etc., there are two issues I see with unnecessary else-condiditions on if-statements, and un-braced 1-liners. Additionally, white-space around punctuation and operators is useful for readability. This code:

  if( size1  != size2)           
       return false;
   else
   {        
       std::set<int> first_set(array1, array1+size1);
       std::set<int> second_set(array2, array2+size2);

       std::pair<std::set<int>::iterator,std::set<int>::iterator> myPair=std::mismatch(first_set.begin(),first_set.end(),second_set.begin());

       if( *myPair.first != *myPair.second)

            return false;
        else
            return true;
   }

should be written:

if( size1 != size2)
{
    return false;
}
std::set<int> first_set(array1, array1 + size1);
std::set<int> second_set(array2, array2 + size2);

std::pair<std::set<int>::iterator, std::set<int>::iterator> myPair   
   = std::mismatch(first_set.begin(), first_set.end(), second_set.begin());

return *myPair.first == *myPair.second;

Bugs

The set construct keeps just a single entry for all instances of a given value. Thus, for example, given the input [1,2,3,4,4,4,4] it will have just 4 entries.

This leads to bugs in your code when there are duplicates. For example, your code will identify the following two input arrays as being permutations of each other:

[1,2,3,4,5,5,5]
[1,1,1,2,3,4,5]

Answer 2

This code runs in \$O(n \log{n})\$ time because a C++ set is a Red-Black tree, and insertions/deletions/finds run in \$O(\log{n})\$ time. In addition, since you are not using a multiset, your code is not actually correct for arrays with duplicate elements.

In order to resolve this, a simple solution is to use an std::unordered_map (which is a hash table with \$O(1)\$ operations) with the element as the key and the number of occurrences as the value. Construct a map for the 1st and 2nd arrays, and then iterate over the keys (or the array, complexity will be the same) and verify that the values are the same in both maps.

Answer 3

Algorithm and Complexity

As reported in other answers, your program most likely executes in \$O(n.log(n))\$ time and uses \$O(n)\$ extra space, probably substantially more than the original space used by the arrays, and may report erroneous results because of a bad choice of class.

Better algorithm

Forget using anything this sophisticated, this problem can be solved in \$O(n)\$ time with astute brute force, while still using \$O(n)\$ extra space:

• make temporary copies of array1 and array2
• sort both temporary arrays
• compare them -> if equal, result is true, otherwise false.
• free the temporary arrays.

You may think the complexity to be \$O(n.log(n))\$, and it may be so if you use the standard sort method, but keep in mind these arrays are a special case that can be sorted in \$O(n)\$ time using Radix sort

I am not familiar enough with C++ to tell if you will need to implement radix sort yourself or if the standard array sort will perform correctly.

Style

• indentation is inconsistent;
• use white space more systematically and consistently;
• keep line length under control: a limit of 79 characters is advisable;
• the number of elements in the arrays should be computed in a safer way with sizeof(array1) / sizeof(array1[0]) instead of sizeof(array1)/sizeof(int)