Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Let $\texttt{a[]}$ be a finite array. We want to check whether every number between $\texttt {min(a[])}$ and $\texttt {max(a[])}$ appears exactly once.
An obvious solution is sorting the array in time $O(n\log(n))$ and go through the sorted array in linear time and check that $\texttt{a[k+1] == a[k]+1}$ for $0\leq\texttt{k} < \texttt{length(a)-1}$.
The total complexity of this would be again $O(n\log(n))$. Is there a better way to do this?
Let $A$ contain $n$ elements. Scan $A$ to determine the maximum value $m$ in $A$. Then, initialize a bit vector $B$ of size $m$ to all zeros. Then scan $A$ and use $B$ for bookkeeping: when you encounter $i$ in $A$, set $B[i]$ to one (if $B[i]$ is already set, return false). In the end, return true if and only if $B$ contains exactly $n$ ones. This algorithm runs in $\Theta(n+m)$ time, or even in $\Theta(n)$ time if we assume $m = O(n)$.
We can also be a little bit more clever with David Richerby's idea. Let us scan $A$ to find its minimum value $s$. Then initialize an array $B$, this time of size $n$, to all zeros. Go through $A$ again, and when you encounter the value $i$ in $A$: if $i - s > n$ or $B[i-s]=1$, return false. Otherwise, set $B[i-s]=1$. Obviously, this algorithm runs in $\Theta(n)$ time (independent of $m$).
In both cases we assume reading the index of an array is done in unit time, and also that arbitrary width arithmetic is performed in unit time.
O(1): 1. Clear the array 2. return false ;) $\endgroup$