2

Possible Duplicate:
Check if array B is a permutation of A

Is there a way to tell if two arrays of numbers (which can contain positives, negatives or repeats) are permutations of each other in O(n) time complexity and O(1) space complexity? I could not solve it because of tight space constraints.

Community
  • 1
  • 1
Peter
  • 2,719
  • 4
  • 25
  • 55

2 Answers2

2

If the numbers are integers - in-place radix sort can give you O(nlogk) time, where k is the range of the numbers, and n is the number of elements.
Note that the algorithm requires O(logk) space, for the stack trace of recursive calls.
If you can bound k to a constant (2^64 for example) - you get O(n) time with O(1) space.

After sorting - you can simply iterate on both arrays and check if they are identical.

amit
  • 175,853
  • 27
  • 231
  • 333
0

It can be done if you have a hard limit on the range of the numbers themselves.

Say for example you know that you have two arrays A and B and that the numbers are bound between -128 and +127(8bit signed). You simply have an array of 256 locations. Each number n would map to the location n + 128.

You iterate over both arrays, for array A you would increment the corresponding location, for array B you decrement. Then you check if all locations are 0 or not. If they are, the arrays are permutations, if not, they aren't.

The time complexity is O(n+k). The space complexity is O(k) where k is the range of the numbers. Since k is independent of n, so that's O(n) and O(1) as far as n is concerned and as long as you have a bound on k.

Note also that the time complexity can be further reduced to simply O(n) instead of O(n+k). You simply keep a running total of numbers that have non-zero counts. Every time an increment/decrement would push a count from to something else, you increment the running total. Every time it would be pushed to zero, you decrement the total. At the end, if the total is 0, then all counts are 0.

Edit: Amit's answer probably has a better space complexity though :)

PS: However, this algorithm can be applied if the arrays of numbers are streamed in, so they never actually have to be all kept in memory. So it might have a smaller space complexity than outright sorting if the conditions are right

entropy
  • 3,134
  • 20
  • 20
  • Using a hash map rather then a fixed size array can bring the space requirement down to `O(min{k,n})`, using the same approach. – amit Jul 15 '12 at 08:20
  • Yep, both are true, that was just an example. Also, amit's suggestion is the general case of that. `(add 128)` can be a hash function itself. So the general case is to just use a hashmap. – entropy Jul 15 '12 at 08:37