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.

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.";

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

StackExchange Computer Science Q#69064, answer score: 2