Solution

The numbers are in the range

$0$ to $n^2-1$

Using radix sort with base $n$, each number can be represented using $2$ digits.

Radix sort takes

$O(d(n+b))$

Here,

$d=2$ and $b=n$

So,

$O(2(n+n))=O(n)$

Hence, the best running time is $O(n)$.