6
$\begingroup$

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

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

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Husrev Jan 21 '17 at 15:42
  • $\begingroup$ 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. $\endgroup$ – Malgorythm Jan 21 '17 at 15:47
  • 1
    $\begingroup$ 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). $\endgroup$ – D'Nabre Jan 21 '17 at 17:31
  • $\begingroup$ 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. $\endgroup$ – D'Nabre Jan 21 '17 at 17:37
  • 1
    $\begingroup$ @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]$. $\endgroup$ – Socowi Jan 21 '17 at 19:45
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ Can you explain your algorithm in English so that people not conversant in python can understand it as well? $\endgroup$ – Yuval Filmus Jan 30 '17 at 8:28
  • $\begingroup$ I have added an outline of the algorithm; but I think the Python code is already very close to pseudocode. $\endgroup$ – Catalin P Jan 31 '17 at 2:07
  • $\begingroup$ 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. $\endgroup$ – styrofoam fly Feb 10 '17 at 23:59
  • $\begingroup$ @styrofoamfly you're right. I hoisted seen up to reuse it across runs to avoid clearing it. What do you think? $\endgroup$ – Catalin P Feb 11 '17 at 19:17
  • $\begingroup$ @CatalinPatulea It seems like a good idea, I like it. $\endgroup$ – styrofoam fly Feb 15 '17 at 17:30
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.