# Algorithm with $O(n)$ time and $O(n)$ space to compare two arrays

$A$ and $B$ are two arrays with $n$ elements each in the range $1$ to $n^2$.

1.How to check if the elements of $A$ are distinct in $O(n)$ time and $O(n)$ space

2.How to check if $A$ and $B$ have a common element in $O(n)$ time and $O(n)$ space.

Both the algorithms shouldn't use Hash sets or any other advanced data structure. A and B are just simple Arrays.

• Hint: A number in the range $0$ to $n^2-1$ can be thought of as a two-digit number in base $n$. – Pseudonym Jan 21 '17 at 7:52
• Also note that 2 almost gives you the answer for 1 if you take $B$ "similar to" $A$. – Keelan Jan 21 '17 at 8:17
• In which model? – Raphael Jan 21 '17 at 12:21
• Are you confident the can be don in O(n)? – paparazzo Jan 22 '17 at 0:41
• No, I need to know if they can be done? – Malgorythm Jan 22 '17 at 1:34

A HashSet can store $n$ elements in $\mathcal{O}(n)$ space and add/query elements in amortized $\mathcal{O}(1)$ time. Therefore we can use the following approaches:

1. Are A's values distinct?

HashSet setA;
for i in {1, ..., n}
if setA.contains(A[i])
return "No, A[i] is a duplicate.";
endif
endfor
return "Yes, values are distinct.";


2. Do A and B intersect?

HashSet setA, setB;
for i in {1, ..., n}
if setB.contains(A[i]) or setA.contains(B[i])
return "Yes, A and B intersect.";
endif
endfor
return "No, A and B are disjoint.";


Edit: Thanks to D'Nabre for pointing out a problem. The assumed $\mathcal{O}(1)$ for querying the HashSets may not work out in this case. D'Nabre also pointed at the element distinctness problem, which is worth a look. From Wikipedia:

it may also be solved in linear expected time by a randomized algorithm that inserts each item into a hash table and compares only those elements that are placed in the same hash table cell.

• Since I am not coming from a CS background, I couldn't comprehend how '.contains()' query is done in $\mathcal{O}(1)$ since the range is 1 to $n^2$ while your space complexity is $\mathcal{O}(n)$. And why do you loop up to $n$ instead of $n^2$? – Husrev Jan 21 '17 at 15:42
• Thanks. Can we do it without using the Hash Sets.Both the algorithms shouldn't use Hash sets or any other advanced data structure. A and B are just arrays. – Malgorythm Jan 21 '17 at 15:47
• Insertions into a HashSet are O(1) average amortized time, under assumptions like perfect hashing and what not. Worse-case is O(n). Part 1. is exactly the element uniqueness problem and has a provable lower-bound of O(n log n). – D'Nabre Jan 21 '17 at 17:31
• addition There are some restrictions that are likely the key to getting around the element-uniqueness lower bound, but the general case it isn't possible. – D'Nabre Jan 21 '17 at 17:37
• @Husarev The arrays have $n$ entries. Each entry is a number from the range $1$ to $n^2$. Example: Let $n=3$. A concrete problem case could be $A=[9, 9, 1]$ and $B=[2, 7, 5]$. – Socowi Jan 21 '17 at 19:45

The principle is similar to radix sort; then check uniqueness in each bucket.

• Prepare n lists of elements (buckets), initially empty
• For each element x:
• Separate x into its two digits msd (most significant digit) and lsd in base n.
• Append lsd to the end of the msd'th list
• Iterate through all buckets, check that each lsd in each list is unique. If not, some number x was added twice.

--

n = ...

def unique1(xs, seen):
"""Are the values of xs (0 to n-1) unique? O(len(xs))"""
unique = True
for x in xs:
if seen[x]:
unique = False
break
seen[x] = True
# Clear seen[] for next run.
for x in xs:
seen[x] = False
return unique

def unique2(xs):
"""Are the values of xs (0 to n^2-1) unique? O(n)"""

# Sort xs into buckets by most significant digit. n buckets containing
# len(xs) (= n) elements in total, so O(n) space.
buckets = [[] for _ in range(n)]
for x in xs:
msd, lsd = divmod(x, n)
buckets[msd].append(lsd)

# Check uniqueness in each bucket. In total len(xs) values are passed to
# unique1, so total O(n) time.
temp = [False] * n
for b in buckets:
if not unique1(b, temp):
return False

return True


Edit: trivial to extend to second question by also storing the source of the element (set A or B) in the buckets.

• Can you explain your algorithm in English so that people not conversant in python can understand it as well? – Yuval Filmus Jan 30 '17 at 8:28
• I have added an outline of the algorithm; but I think the Python code is already very close to pseudocode. – Catalin P Jan 31 '17 at 2:07
• This algoritm is O(n^2), since unique1 is O(n) instead of O(len(xs)). If you want to have a list seen of length len(xs), you don't know where to put True for value 5 (for example). If you make a list of length n, initializing it takes O(n) time. – styrofoam fly Feb 10 '17 at 23:59
• @styrofoamfly you're right. I hoisted seen up to reuse it across runs to avoid clearing it. What do you think? – Catalin P Feb 11 '17 at 19:17
• @CatalinPatulea It seems like a good idea, I like it. – styrofoam fly Feb 15 '17 at 17:30

It would be quite simple if your values were all in the range 0 ≤ k < n: Create an array b of n boolean values initialised to all "false", then for each array element k check whether b [k] is true or false. If b [k] is true then there are duplicates, and if not then set b [k] = true.

Unfortunately, the values are from 0 to n^2 - 1.

For every j, 0 ≤ j < n, build a linked list of all array values k where k = j (modulo n). That can be done in O (n) time and space for all array elements, since all you need to do is initialise n empty lists, and add each array element to one of the lists.

Then for each linked list, use the method above to check whether the values floor (k / n), which are all in the range from 0 to n-1, are unique. The array b is initialised once. Then we check one linked list, and when we are done with that list, we set all elements of b corresponding to list elements back to false. That way the total time is again O (n), since the total number of items in all linked lists is exactly n.

The essential "trick" to not use more than O (n) time is to not initialise the array b each time (O (n), needs to be done n times), but set it to "all false" only once, and then just set those elements back to false that were set to true before.