In two unsorted arrays A and B such that all items of A belong to B (A ⊂ B), find the smallest item in B that doesn't occur in A in linear time?

Question

In two unsorted arrays (say $A$ and $B$) such that all items of $A$ belong to $B$ ($A \subset B$), find the smallest item in $B$ that doesn't occur in $A$ in linear time.

No hashing or linear time sorting is allowed.

I can solve this question when $A$ and $B$ are sorted.
However, the question states $A$ and $B$ are unsorted, and I cannot think of a solution that solves this in O(n) time.

Answer 1

I'm going to assume that all elements in $A$ and $B$ are distinct (this assumption can be removed with some care), that elements possess a linear order, and that they can be compared in constant time.

Consider the following recursive algorithm: if $|A|=0$, return the minimum in $B$ (in time $O(|B|)$). Otherwise, find the median $x$ of the multiset obtained by unioning $A$ and $B$ and partition the elements of $A$ in $A_{\le x}$ and $A_{> x} $ (resp. the elements of $B$ in $B_{\le x}$ and $B_{> x} $) depending on whether they are at most $x$ or larger than $x$. This requires time $O(|A|+|B|)$.

If $|A_{\le x}|=|B_{\le x}|$ then $A \subset B$ implies $A_{\le x}=B_{\le x}$ and you can recurse on $A_{> x} $ and $B_{> x}$.

If $|A_{\le x}| < |B_{\le x}|$ then the minimum element in $B \setminus A$ must be at most $x$ and hence it is in $B_{\le x} \setminus A_{\le x}$ and you can recurse on $A_{\le x}$ and $B_{\le x}$.

Let $n = |A| + |B|$. By the choice of $x$, the input size of the recursive call will be at most $\left\lceil \frac{|A|+|B|}{2} \right\rceil = \lceil n/2 \rceil$, showing that the algorithm eventually terminates (since $n \le 2$ implies $|A|=0$).

To bound the running time we notice that it is described by the recurrence $ T(n) = T(\lceil n/2 \rceil) + O(n) $, which has solution $T(n)=O(n)$.

Answer 2

Reasoning:

• you are asked the smallest in $B$; this hints that the solution will be comparison-based.

• with an $O(n)$ budget, no comparison-based sort is possible; the best you can do with comparisons is to heapify !

• wonder what happens if you heapify the two arrays and compare them.

Notice that after a heapify operation, every array element is the smallest among the subtree of which it is a root. So when you compare the heaps formed from $A$ and $B$, the first discrepancy you will meet when scanning the elements will reveal the solution.

E.g.

$$A= [1,2,3,4,6],\\ B= [6,2,4,7,1,5,3]$$

heapify as

$$A=[1, 2, 3, 4, 6],\\B= [1, 2, 3, \color{green}7, 6, 5, 4].$$