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

$\endgroup$
5
  • 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, 2017 at 7:52
  • $\begingroup$ Also note that 2 almost gives you the answer for 1 if you take $B$ "similar to" $A$. $\endgroup$
    – user23039
    Jan 21, 2017 at 8:17
  • $\begingroup$ In which model? $\endgroup$
    – Raphael
    Jan 21, 2017 at 12:21
  • $\begingroup$ Are you confident the can be don in O(n)? $\endgroup$
    – paparazzo
    Jan 22, 2017 at 0:41
  • $\begingroup$ No, I need to know if they can be done? $\endgroup$
    – Malgorythm
    Jan 22, 2017 at 1:34

3 Answers 3

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.

$\endgroup$
9
  • $\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, 2017 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, 2017 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, 2017 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, 2017 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, 2017 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.

$\endgroup$
5
  • 3
    $\begingroup$ Can you explain your algorithm in English so that people not conversant in python can understand it as well? $\endgroup$ Jan 30, 2017 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, 2017 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$ Feb 10, 2017 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, 2017 at 19:17
  • $\begingroup$ @CatalinPatulea It seems like a good idea, I like it. $\endgroup$ Feb 15, 2017 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.

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