Space complexity for finding the minimum number outside the list of numbers

Question

We are given an (unsorted) list $L=(a_1,\dots,a_n)$ of numbers of size $n$, where $a_i\in \{ 1,\dots,B\}$.

We want to find the minimum number $x$ from $\{ 1,\dots,B\} \backslash L$.

What is the space complexity of this problem ? (The space to store the input, $L$, does not count.) What if the input $L$ is in a stream which you can only read from left to right for at most constant number of passes ?

The obvious way to solve this is just to copy $L$ into the working memory and then (in-place) sort $L$, and find $x$ in the obvious way. This algorithm uses space of size $n$.

Can we do better ?

Answer 1

You can solve this in time $O(n\log B)$ and constant space (assuming a machine word can store numbers up to $\max(n,B)$) using binary search.

Edit: Here are some more details. I am making the assumption that no number appears twice - perhaps that's an unfounded assumption. Given $K$, we can check whether $K<L$, $K=L$ or $K>L$ by counting how many numbers smaller than $K$ appear in the input, and whether $K$ itself appears in the input. This takes $O(n)$.

Edit 2: Following eig's suggestion, since we know that the missing number is smaller than $n+2$, this actually takes time $O(n\log n)$.

Answer 2

For your second question, one can obtain some space bounds for deterministic streaming. (See Sasho Nikolov's answer for the randomized single-pass case.)

If $n$ is constant, you can find the minimum using $\lceil \log_2 B \rceil$ bits, by storing the smallest element not seen so far, and streaming the list $n$ times. Each pass is guaranteed to either result in the minimum, or to disqualify one (or more, if there are repeats) of the $n$ elements of the list.

I presume you actually meant that $n$ should not be fixed.

Then with single-pass deterministic streaming, one has to use at least $B$ bits of space. This is required to distinguish the different choices of the list $L$, by an application of the single-pass streaming Comparison Lemma (see ECCC TR12-183 for details about the technique). The intuition is that if fewer bits are kept, then there are two input streams that represent two different subsets of $B$ which end up with the same internal state; an adversary can then add numbers to the end of the stream to ensure that the algorithm gives the wrong answer. For an upper bound, $B + 2\lceil \log B \rceil$ bits is enough. Keep an array of $B$ bits, a variable to index to the array, and a temporary variable. Initially the array entries are set to 0. Change the bit for $i$ to 1 if $i$ is read. The first 0 entry in the array gives the right answer. So the lower bound of $B$ bits is nearly tight for single-pass deterministic streaming.

I have not seen this problem before, and I do not know what the bounds would be for more than 1 but less than $n$ passes. See also a similar question of mine at CSTheory.

Edit: expanded and corrected the single-pass bounds.

Answer 3

An easy reduction from the Index problem shows a lower bound of $\Omega(B)$ for single pass randomized algorithms. Recall that in the Index problem Alice is given a subset $S$ of $U$ and Bob is given an element $e$ of $U$. The goal is to compute whether $e \in S$. The (randomized) one-way communication complexity of Index is $\Omega(|U|)$.

For the reduction, let us identify $U$ with $\{1, \ldots, B\}$, i.e. fix some bijection $f$ between $U$ and $\{1, \ldots, B\}$. For an instance $(S, e)$ of the Index problem, let $L_0 = \{1, \ldots, B\} \setminus f(S)$, where $f(S) = \{f(a): a \in S\}$; let $L_1 = \{i: i < f(e)\}$. The stream consists of $L_0$ followed by $L_1$. Clearly the minimum number not in $L = L_0 \cup L_1$ is at least $f(e)$, because $L_1$ includes all numbers smaller than $f(e)$. If $e \in S$, then $L_0$ does not include $f(e)$ and the minimum number outside $L$ is at least $f(e) + 1$; otherwise the minimum is $f(e)$.

As usual, Alice can process $L_0$ using the streaming algorithm, send the contents of memory to Bob, who then uses the memory to process $L_1$ and compute the final answer and decide whether $f \in S$. This gives a one-way communication protocol for Index with communication complexity at most the space complexity of the streaming protocol, and, because the communication complexity is at least $\Omega(|U|) = \Omega(B)$, the space complexity is at least as many bits as well. Obviously this is tight up to constants for single-pass streaming.

Answer 4

Suppose instead that you're interested in the parity of $x$. Consider the two-player communication scenario where one player gets the even half of $L$ and the other player gets the odd half of $L$. It seems plausible that the deterministic communication complexity of this game is $\Omega(n)$, and so the usual argument would give an $\Omega(n)$ bits space lower bound.