$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.
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
setA.add(A[i])
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
setA.add(A[i]);
setB.add(B[i]);
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.
The principle is similar to radix sort; then check uniqueness in each bucket.
--
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.
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.
$\endgroup$
– styrofoam fly
Feb 10 '17 at 23:59
seen up to reuse it across runs to avoid clearing it. What do you think?
$\endgroup$
– Catalin P
Feb 11 '17 at 19:17
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.
