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

Question

$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.

Answer 1

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.

Answer 2

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.

Answer 3

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.