0

I want to check whether two arrays are equal or not without sorting them and also the order of the elements can be different in arrays.

I am thinking about taking the sum but it will not work in the following case:-

A = [4,2] B = [1,5]

One way of doing this is to create a hash map and check the frequency but that will require extra O(n) space and I want to do it without using any extra space.

Atul Agrawal
  • 1,474
  • 5
  • 22
  • 41
  • 2
    The only way is to break one of your requirements -- you either have to modify the arrays (sort them), use O(n) extra space, or resort to O(n^2) efficiency by brute force (for each element in A, count the number of occurrences, then verify that B also has the same number of occurrences). – k_ssb Jun 01 '18 at 07:21
  • Maybe not relevant for your case, but if there are repeated elements counting frequencies can be much better than O(n). For example, if you to lists of bytes with ten million elements each, you only need to count the frequency of up to 255 elements. – jdehesa Jun 01 '18 at 10:04
  • @jdehesa Counting the frequency of a particular element still takes O(n) time (you need to look at every element of the array). But you're right that you can count frequencies of fewer than O(n) elements. By the way, there are 256 distinct byte values. – k_ssb Jun 01 '18 at 10:56
  • @pkpnd Hah, you're right, obviously I was thinking of "the frequency of elements from 0 to 255", but it's not the first I make that mistake! :/ I should have specified, when I said "much better than O(n)" I was referring to space complexity, like you said time complexity is of course O(n). – jdehesa Jun 01 '18 at 11:00
  • Can you accept very rare false positives? If so could compute a function of the elements (e.g. a hash), and then sum that instead/in addition to the element-values. With a suitable function the probability of two arrays having the same sum can be sufficiently small. – Hans Olsson Jun 01 '18 at 13:31
  • How large are your arrays? What data type? In general, the comments above are true: this either requires O(n) extra space or O(n^2) time. But there are possible tricks for special cases. – Jim Mischel Jun 01 '18 at 13:40
  • This is a duplicate/very similar to https://stackoverflow.com/questions/6691184/find-if-two-arrays-contain-the-same-set-of-integers-without-extra-space-and-fast – Gijs Den Hollander Jun 01 '18 at 14:50
  • Possible duplicate of [find if two arrays contain the same set of integers without extra space and faster than NlogN](https://stackoverflow.com/questions/6691184/find-if-two-arrays-contain-the-same-set-of-integers-without-extra-space-and-fast) – Shubham Jun 02 '18 at 06:50

0 Answers0