Take the 2-minute tour ×

I tried to find a solution to this but couldn't get much out of my head.

We are given two unsorted integer arrays A and B. We have to check whether array B is a permutation of A. How can this be done.? Even XORing the numbers wont work as there can be several counterexamples which have same XOR value bt are not permutation of each other.

A solution needs to be O(n) time and with space O(1)

Any help is welcome!! Thanks.

share|improve this question
Are you allowed to sort them? –  wildplasser May 17 '12 at 16:29
no, that's not possible. –  Karoly Horvath May 17 '12 at 16:36
Is there an upper bound on the maximum allowed integer? Or can they be arbitrary-precision integers? –  templatetypedef May 17 '12 at 16:43
If the integers can be arbitrary precision then 'n' in 'O(n)' needs to include the encoding size of all the integers and cannot represent the number of elements in the array per se. –  Antti Huima May 17 '12 at 17:27
Note that if the integers are arbitrary precision, things like multiplication suddenly don't work as O(1) operations anymore, as they tend to work for practical algorithm analysis purposes on register-size integers. The multiplication of two O(n) bigints, say, is not O(n) operation. I bet the question wasn't actually about "arbitrary precision integers", but about unspecified (but limited) precision. Anyway, maybe this part of the question should be re-checked. –  Antti Huima May 17 '12 at 17:36

9 Answers 9

The question is theoretical but you can do it in O(n) time and o(1) space. Allocate an array of 232 counters and set them all to zero. This is O(1) step because the array has constant size. Then iterate through the two arrays. For array A, increment the counters corresponding to the integers read. For array B, decrement them. If you run into a negative counter value during iteration of array B, stop --- the arrays are not permutations of each others. Otherwise at the end (assuming A and B have the same size, a prerequisite) the counter array is all zero and the two arrays are permutations of each other.

This is O(1) space and O(n) time solution. However it is not practical, but would easily pass as a solution to the interview question. At least it should.

More obscure solutions

  • Using a nondeterministic model of computation, checking that the two arrays are not permutations of each others can be done in O(1) space, O(n) time by guessing an element that has differing count on the two arrays, and then counting the instances of that element on both of the arrays.

  • In randomized model of computation, construct a random commutative hash function and calculate the hash values for the two arrays. If the hash values differ, the arrays are not permutations of each others. Otherwise they might be. Repeat many times to bring the probability of error below desired threshold. Also on O(1) space O(n) time approach, but randomized.

  • In parallel computation model, let 'n' be the size of the input array. Allocate 'n' threads. Every thread i = 1 .. n reads the ith number from the first array; let that be x. Then the same thread counts the number of occurrences of x in the first array, and then check for the same count on the second array. Every single thread uses O(1) space and O(n) time.

  • Interpret an integer array [ a1, ..., an ] as polynomial xa1 + xa2 + ... + xan where x is a free variable and the check numerically for the equivalence of the two polynomials obtained. Use floating point arithmetics for O(1) space and O(n) time operation. Not an exact method because of rounding errors and because numerical checking for equivalence is probabilistic. Alternatively, interpret the polynomial over integers modulo a prime number, and perform the same probabilistic check.

share|improve this answer
+1 thats very slick –  goat May 17 '12 at 16:54
I don't see how you can claim O(1) space when you assume a maximum and just pre-allocate it. If I used that criteria, I could claim that any algorithm is O(1) space so long as you allocate enough before you start. –  David Buck May 17 '12 at 17:01
? The size of the array depends on the size of unsigned int. –  Antti Huima May 17 '12 at 17:04
Ok, so if you used arbitrary precision integers? Smalltalk for example has unlimited Integer precision. The question never said "unsigned int". This is a question about algorithmic complexity, not implementation in a language that only supports 32 bit unsigned ints. –  David Buck May 17 '12 at 17:09
This is not a generally correct answer. –  Jason May 17 '12 at 18:09

I apologize for posting this as an answer as it should really be a comment on antti.huima's answer, but I don't have the reputation yet to comment.

The size of the counter array seems to be O(log(n)) as it is dependent on the number of instances of a given value in the input array.

For example, let the input array A be all 1's with a length of (2^32) + 1. This will require a counter of size 33 bits to encode (which, in practice, would double the size of the array, but let's stay with theory). Double the size of A (still all 1 values) and you need 65 bits for each counter, and so on.

This is a very nit-picky argument, but these interview questions tend to be very nit-picky.

share|improve this answer

If we are allowed to freely access a large list of primes, you can solve this problem by leveraging properties of prime factorization.

For both arrays, calculate the product of Prime[i] for each integer i, where Prime[i] is the ith prime number. The value of the products of the arrays are equal iff they are permutations of one another.

Prime factorization helps here for two reasons.

  1. Multiplication is transitive, and so the ordering of the operands to calculate the product is irrelevant. (Some alluded to the fact that if the arrays were sorted, this problem would be trivial. By multiplying, we are implicitly sorting.)
  2. Prime numbers multiply losslessly. If we are given a number and told it is the product of only prime numbers, we can calculate exactly which prime numbers were fed into it and exactly how many.


a = 1,1,3,4
b = 4,1,3,1
Product of ith primes in a = 2 * 2 * 5 * 7 = 140
Product of ith primes in b = 7 * 2 * 5 * 2 = 140

That said, we probably aren't allowed access to a list of primes, but this seems a good solution otherwise, so I thought I'd post it.

share|improve this answer
This is not worse than hashing. Instead of accessing prime nos., we can have hash table of the range of numbers that will be gotten as input in a & b and do it. In turn hash table can be reduced in size by using bits. –  viji Jul 27 '12 at 14:05

If we need not sort this in-place, then the following approach might work:

  1. Create a HashMap, Key as array element, Value as number of occurances. (To handle multiple occurrences of the same number)
  2. Traverse array A.
  3. Insert the array elements in the HashMap.
  4. Next, traverse array B.
  5. Search every element of B in the HashMap. If the corresponding value is 1, delete the entry. Else, decrement the value by 1.
  6. If we are able to process entire array B and the HashMap is empty at that time, Success. else Failure.

HashMap will use constant space and you will traverse each array only once.

Not sure if this is what you are looking for. Let me know if I have missed any constraint about space/time.

share|improve this answer

You're given two constraints: Computational O(n), where n means the total length of both A and B and memory O(1).

If two series A, B are permutations of each other, then theres also a series C resulting from permutation of either A or B. So the problem is permuting both A and B into series C_A and C_B and compare them.

One such permutation would be sorting. There are several sorting algorithms which work in place, so you can sort A and B in place. Now in a best case scenario Smooth Sort sorts with O(n) computational and O(1) memory complexity, in the worst case with O(n log n) / O(1).

The per element comparision then happens at O(n), but since in O notation O(2*n) = O(n), using a Smooth Sort and comparison will give you a O(n) / O(1) check if two series are permutations of each other. However in the worst case it will be O(n log n)/O(1)

share|improve this answer

The solution needs to be O(n) time and with space O(1). This leaves out sorting and the space O(1) requirement is a hint that you probably should make a hash of the strings and compare them.

If you have access to a prime number list do as cheeken's solution.

Note: If the interviewer says you don't have access to a prime number list. Then generate the prime numbers and store them. This is O(1) because the Alphabet length is a constant.

Else here's my alternative idea. I will define the Alphabet as = {a,b,c,d,e} for simplicity. The values for the letters are defined as:

a, b, c, d, e
1, 2, 4, 8, 16

note: if the interviewer says this is not allowed, then make a lookup table for the Alphabet, this takes O(1) space because the size of the Alphabet is a constant

Define a function which can find the distinct letters in a string.

// set bit value of char c in variable i and return result
distinct(char c, int i) : int

E.g. distinct('a', 0) returns 1
E.g. distinct('a', 1) returns 1
E.g. distinct('b', 1) returns 3

Thus if you iterate the string "aab" the distinct function should give 3 as the result

Define a function which can calculate the sum of the letters in a string.

// return sum of c and i
sum(char c, int i) : int

E.g. sum('a', 0) returns 1
E.g. sum('a', 1) returns 2
E.g. sum('b', 2) returns 4

Thus if you iterate the string "aab" the sum function should give 4 as the result

Define a function which can calculate the length of the letters in a string.

// return length of string s
length(string s) : int

E.g. length("aab") returns 3

Running the methods on two strings and comparing the results takes O(n) running time. Storing the hash values takes O(1) in space.

 distinct of "aab" => 3
 distinct of "aba" => 3
 sum of "aab => 4
 sum of "aba => 4
 length of "aab => 3
 length of "aba => 3

Since all the values are equal for both strings, they must be a permutation of each other.

EDIT: The solutions is not correct with the given alphabet values as pointed out in the comments.

share|improve this answer
This does not work, because "bccabcde" and "ddaabcde" have the same sum (10 + 31), length (8) and "distinct" (all), but the strings are not permutations of each other. –  Antti Huima Mar 17 at 10:56
@AnttiHuima I calculate "bccabcde" as 41 and "ddaabcde" as 48 function hash(str){var arr = {'a':1, 'b':2, 'c':4, 'd':8, 'e':16}; return str.split('').reduce(function(a,b){ return a + arr[b]; }, 0); } –  Kunukn Mar 17 at 21:05
Yes, sorry, it was a typo. It should be "bccabcde" and "daaabcde", i.e. the second string starts "daa... " instead of "dda". The point is that b+c+c = 4+4+2 = 10 and d+a+a = 8+1+1 = 10, so the sums become equal. Sorry about the typo. –  Antti Huima Mar 18 at 9:04
You are right, have updated the EDIT info for the post. –  Kunukn Mar 18 at 10:49

You can convert one of the two arrays into an in-place hashtable. This will not be exactly O(N), but it will come close, in non-pathological cases.

Just use [number % N] as it's desired index or in the chain that starts there. If any element has to be replaced, it can be placed at the index where the offending element started. Rinse , wash, repeat.

UPDATE: This is a similar (N=M) hash table It did use chaining, but it could be downgraded to open addressing.

share|improve this answer
Could you elaborate on in-place hashtable? I don't see how you can store the hashtable in exactly the same space as an array, so you'd almost certainly be violating the O(1) space requirement. –  Jimmy May 17 '12 at 17:17
Yes, you can permute the array in such a way that it forms a hash table with open addressing, say linear probing. That is typically an O(N) process. Open addressing does not need additional space. I am working on it... See for instance my tinyhash contribution here, which used N slots for N entries. (which did do sorting, but that is not strictly necessary) –  wildplasser May 17 '12 at 17:29
After you use linear probing and have 100% load factor, iterating through the array is no longer O(n) process but O(n^2) or something like that. –  Antti Huima May 17 '12 at 17:43
No. It is still O(N). Average "(mean square) chain length" will be about 1.5. See the histogram in my link. Constructing it will be of similar complexity (but is harder, caused by the space constraint) –  wildplasser May 17 '12 at 18:20
But the input could be pathological that maps every input to the same bucket / chain. It does not matter if for some random number distributions the chain length is linear. –  Antti Huima May 18 '12 at 5:56

I'd use a randomized algorithm that has a low chance of error.

The key is to use a universal hash function.

def hash(array, hash_fn):
  cur = 0
  for item in array:
    cur ^= hash_item(item)
  return cur

def are_perm(a1, a2):
  hash_fn = pick_random_universal_hash_func()
  return hash_fn(a1, hash_fn) == hash_fn(a2, hash_fn) 

If the arrays are permutations, it will always be right. If they are different, the algorithm might incorrectly say that they are the same, but it will do so with very low probability. Further, you can get an exponential decrease in chance for error with a linear amount of work by asking many are_perm() questions on the same input, if it ever says no, then they are definitely not permutations of each other.

share|improve this answer

I just find a counterexample. So, the assumption below is incorrect.

I can not prove it, but I think this may be possible true.

Since all elements of the arrays are integers, suppose each array has 2 elements, and we have

a1 + a2 = s
a1 * a2 = m

b1 + b2 = s
b1 * b2 = m

then {a1, a2} == {b1, b2}

if this is true, it's true for arrays have n-elements.

So we compare the sum and product of each array, if they equal, one is the permutation of the other.

share|improve this answer
Not true: [0,0,2] and [0,1,1] –  Rafał Dowgird May 18 '12 at 21:58
since there is a multiplication, we should take care of zero in the arrays. we can just count the number of zeros in each array and exclude that in the sums and the products. –  uncle_xia May 19 '12 at 4:52

Your Answer


