CODEWITHSUNDEEP
arrays
Bruce
Bruce

Reputation: 35275

Find if one integer array is a permutation of other

Given two integer arrays of size N, design an algorithm to determine whether one is a permutation of the other. That is, do they contain exactly the same entries but, possibly, in a different order.

I can think of two ways: Sort them and compare : O(N.log N + N)

Check if the array have same number of integers and the sum of these integers is same, then XOR both the arrays and see if the result is 0. This is O(N). I am not sure if this method will eliminate false positives completely. Thoughts. Better algorithms?

Upvotes: 2

Views: 1822

Answers (4)

Mark Byers
Mark Byers

Reputation: 838376

Check if the array have same number of integers and the sum of these integers is same, then XOR both the arrays and see if the result is 0.

This doesn't work. Example:

a = [1,6]  length(a) = 2, sum(a) = 7, xor(a) = 7
b = [3,4]  length(b) = 2, sum(b) = 7, xor(b) = 7

Others have already suggested HashMap for an O(n) solution.

Here's an O(n) solution in C# using a Dictionary<T, int>:

bool IsPermutation<T>(IList<T> values1, IList<T> values2)
{
    if (values1.Count != values2.Count)
    {
        return false;
    }

    Dictionary<T, int> counts = new Dictionary<T, int>();
    foreach (T t in values1)
    {
        int count;
        counts.TryGetValue(t, out count);
        counts[t] = count + 1;
    }

    foreach (T t in values2)
    {
        int count;
        if (!counts.TryGetValue(t, out count) || count == 0)
        {
            return false;
        }
        counts[t] = count - 1;
    }

    return true;
}

In Python you could use the Counter class:

>>> a = [1, 4, 9, 4, 6]
>>> b = [4, 6, 1, 4, 9]
>>> c = [4, 1, 9, 1, 6]
>>> d = [1, 4, 6, 9, 4]
>>> from collections import Counter
>>> Counter(a) == Counter(b)
True
>>> Counter(c) == Counter(d)
False

Upvotes: 3

Jo&#227;o Silva
Jo&#227;o Silva

Reputation: 91329

If a space complexity of O(n) is not a problem, you can do it in O(n), by first storing in a hash map the number of occurrences for each value in the first array, and then running a second pass on the second array and check that every element exists in the map, decrementing the number the occurrences for each element.

Upvotes: 2

Don Roby
Don Roby

Reputation: 41137

The best solution is probably a counting one using a map whose keys are the values in your two arrays.

Go through one array creating/incrementing the appropriate map location and go through the other one creating/decrementing the appropriate map location.

If the resulting map consists entirely of zeros, your arrays are equal.

This is O(N), and I don't think you can do better.

I suspect this is approximately what Mark Byers was going for in his answer.

Upvotes: 2

rick
rick

Reputation: 165

Sort the contents of both arrays numerically, and then compare each nth item.

You could also take each item in array1, and then check if it is present in array2. Keep a count of how many matches you find. At the end, the number of matches should equal the length of the arrays.

Upvotes: 0

Related Questions