6
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Assuming mutable arrays, this can be done in O(1): 1. Clear the array 2. return false ;) $\endgroup$
    – blubb
    Mar 12, 2015 at 21:23

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ So isn't the linear-time algorithm really to get the min and max $m$ and $M$. Check that $M - m = n - 1$, and say no otherwise. Then use counting sort, which runs in $O(n + M - m) = O(n)$. $\endgroup$
    – Louis
    Mar 12, 2015 at 15:01
  • $\begingroup$ This assumes constant time array access for arrays of size $n$. Can we do better than $O(n\log(n))$ if we don't have such arrays? $\endgroup$
    – cody
    Mar 17, 2015 at 19:35

Not the answer you're looking for? Browse other questions tagged or ask your own question.