Injectivity verification in o(n) space and O(n) time
You haven't specified your exact computation model, so let me assume that you measure space in words of length $\Theta(\log n)$, and that each element in the array occupies one word. Let me assume furthermore that you can compare two elements in constant time.

The oracle should provide you with the relative order of the elements, say as an array $B$ whose entries are the numbers $1,\ldots,n$ in the appropriate order. This advice takes $O(n)$ words, and can be verified in $O(n)$ time and $O(1)$ additional space.

In slightly more detail, here is the verification algorithm:

for i from 1 to n:
  verify that 1 ≤ B[i] ≤ n
for i from 2 to n:
  verify that A[B[i-1]] &lt; A[B[i]]


Let us prove that  there exists an array $B$ for which the verification succeeds iff $A$ consists of distinct elements.

$\longleftarrow$ Suppose that $A$ consists of distinct elements. Order $A$ in increasing order: $A[j_1] &lt; \cdots &lt; A[j_n]$. If we take $B[i] = j_i$ then the verification will succeed.

$\longrightarrow$ Suppose that the verification succeeds for some array $B$. Then $A[B[1]] &lt; \cdots &lt; A[B[n]]$. This implies that $A$ contains at least (and so exactly) $n$ distinct elements.