<p>Here are two solutions which (as suggested in the question and comments) assume that all the given sets are disjoint and performs destructive set unions (when we find the union of sets A and B, we remove A and B themselves from the family of sets).</p>

<p><strong>Amortized constant time</strong></p>

<p>We maintain objects for the sets and objects for the elements. The sets know what elements they have, as a concatenable list, so that we can list those elements quickly, but we don't keep pointers from the objects to the sets that contain them (because it would be too slow to update them).</p>

<p>There is at most one special set Z, the one containing zero. Every object knows whether it is part of Z or not (a binary flag). The set Z maintains the value of its mex. For every other set, the mex is zero. So you can compute the mex of a set in constant time, given either the set itself or one of its elements.</p>

<p>To form the union of two sets, if neither one is Z, just concatenate their lists. If one of the two sets is Z, run through its elements setting the flag that says the element is now in Z. Then, while the mex is an element of Z, increment it.</p>

<p>Each element accounts for one increment operation to the mex of Z, so the amortized time per element, merge, or mex request is constant.</p>

<p><strong>Worst-case logarithmic time</strong></p>

<p>For a worst-case rather than amortized (but slower) solution, that also allows for creation of new singleton sets and does not assume that the union of all the sets is a contiguous interval, we use the following data structures:</p>

<ul>
<li>union-find rather than flags to determine the set that contains any element (even if we just do union-by-rank without path compression, this is worst-case logarithmic per find operation)</li>
<li>a binary search tree of the elements in the union of all the sets</li>
<li>for each element, the smallest non-element between it and its predecessor in the binary search tree (or zero if it has no predecessor)</li>
<li>for each binary search tree node, the smallest non-element listed in its subtree (updated in constant time per tree rotation)</li>
<li>the smallest element of each set</li>
<li>a priority queue of the smallest elements of sets that are not Z.</li>
</ul>

<p>Then at all times mex(Z) is the minimum of the priority queue value and the smallest non-element. And as before, for sets that are not Z, the mex is zero. Adding a new singleton set, merging two sets, or finding a mex all take logarithmic time with more-or-less obvious updates.</p>

CC BY-SA 3.0
2015-12-21T08:25:00.907Z
2015-12-21T08:25:00.907Z
David Eppstein
<p>Do you know of any data structure $S[A]$, that maintains a (finite) set $A \subset \mathbb{Z}_{\geq0}$ of non-negative integers, subject to the following operations:</p>

<ol>
<li>Given $S[A],$ calculate minimal excludant $\mbox{mex} A = \min \ \mathbb{Z_{\geq 0}} \setminus  A.$</li>
<li>Given two data structures for sets $A$ and $B$, construct a data structure, maintaining the union of the two $S[A \cup B]$.</li>
</ol>

<p>Disjoint set union comes into mind, but I can't think of a way to make it support mex-es.
Intuitively, the problem I see is that we can have a situation in which both $A$ and $B$ contain many small intervals, and then their union is hard to obtain.</p>

<p>Ideally, both of these should be polylog (on the size of the represented sets). </p>

<p>How about if the sets are from a bounded universe?</p>

CC BY-SA 3.0
2013-10-22T15:18:09.127Z
What other operations are available? Can I create a structure from any finite set $A$?
jbapple
CC BY-SA 3.0
2013-10-22T18:48:55.313Z
This might be relevant for the bounded universe case: http://arxiv.org/abs/1002.4248
Chao Xu
CC BY-SA 3.0
2013-10-23T00:33:56.570Z
Can you modify the set $A$ after you've created $S[A]$?  If you created $S[A]$, $S[B]$, and $S[A \cup B]$, can you then modify $A$?  If you can, what do you want to have happen in this case?  Do you want both $S[A]$ and $S[A \cup B]$ (and $\operatorname{mex} A$ and $\operatorname{mex} B$) to be updated rapidly?
D.W.
CC BY-SA 3.0
2013-10-23T07:15:29.560Z
@jbapple - We can assume that we could do that. It just boils down to creating $S[\{a\}]$ for each element in $A$, and then taking the union of all these.
comco
CC BY-SA 3.0
2013-10-23T07:17:41.710Z
@D.W. - no, for my use case, set modifications are not allowed, we may assume that $S[A]$ is effectively immutable after creation.
comco
CC BY-SA 3.0
2013-10-23T07:19:23.107Z
@Chao Xu - Looking just at the abstract, this may be exactly what I need!
comco
CC BY-SA 3.0
2013-10-23T11:57:32.910Z
@Chao Xu - the paper you referenced is quite nice, and it discusses supporting predecessor with union in $O(\log n)$ amortized. But I don't see how from these we could compute the minimal excludant.
comco
CC BY-SA 3.0
2013-10-23T16:19:11.477Z
@comco - The merge process described in section 2.1 shows the merge operation finds the min/max of each segment. You can use this information to calculate $mex$ at the same time during each merge. The $O(\log^2)$ amortized bound still holds.
Chao Xu
CC BY-SA 3.0
2013-10-23T17:23:51.180Z
@Chao Xu - In section 2.1, the notion of a segment S of the operation $\mbox{merge}(A, B)$ does not imply that this segment doesn't contain gaps (which are candidates for the mex of the union). For example, for $A = \{1,3,4\}, B = \{4, 5, 6\},$ then $C = \{1,3\}$ is a segment for $\mbox{merge}(A, B),$ but only by knowing its endpoints is not sufficient to check for the numbers which are not inside it (e.a. 2).
comco
CC BY-SA 3.0
2013-10-23T17:27:14.960Z
By thinking about this problem a little bit more, it can be restated as follows: maintain a dynamic collection $\{A_1, A_2, ...\}$ of subsets of ordered universe $U,$ with respect to finding the minimal element of $A_i,$ and finding the intersection of two existing sets (then maybe removing them from collection, and of course, after this operation, C becomes part of the collection and it becomes possible to intersect it with other sets from the collection): $C = A_i \cap A_j.$
comco
CC BY-SA 3.0
2013-10-23T17:57:27.437Z
I see I misinterpreted the definition of the segment. I don't see a obvious solution to this. I wonder if it's possible to argument the DS to return the size of a set in $O(\log n)$ amortized time.
Chao Xu
CC BY-SA 3.0
2013-10-24T11:40:55.927Z
Can some natural number $x$ be in both $S[A]$ and $S[B]$? The analysis in Iacono and Özkan's paper does not apply, if so, I believe.
jbapple
CC BY-SA 3.0
2015-09-01T03:52:04.963Z
Is there an application of this data structure you are thinking of? I thought this was useful for combinatorial game theory, but I can't think games where it's faster to union sets and find mex than just directly maintain a set and find mex.
Chao Xu
<co.combinatorics><ds.data-structures>
Maintain mex with efficient union
comco
# Maintain mex with efficient union

(Asked by: username_0 on 2013-10-22)

Do you know of any data structure $S[A]$, that maintains a (finite) set $A \subset \mathbb{Z}\_{\geq0}$ of non-negative integers, subject to the following operations:

1. Given $S[A],$ calculate minimal excludant $\mbox{mex} A = \min \ \mathbb{Z\_{\geq 0}} \setminus A.$
2. Given two data structures for sets $A$ and $B$, construct a data structure, maintaining the union of the two $S[A \cup B]$.

Disjoint set union comes into mind, but I can't think of a way to make it support mex-es.
Intuitively, the problem I see is that we can have a situation in which both $A$ and $B$ contain many small intervals, and then their union is hard to obtain.

Ideally, both of these should be polylog (on the size of the represented sets).

How about if the sets are from a bounded universe?

**Tags:** co.combinatorics, ds.data-structures

> **Comments:**
> **username_1**: What other operations are available? Can I create a structure from any finite set $A$?  
> **username_2**: This might be relevant for the bounded universe case: http://arxiv.org/abs/1002.4248  
> **username_3**: Can you modify the set $A$ after you've created $S[A]$?  If you created $S[A]$, $S[B]$, and $S[A \cup B]$, can you then modify $A$?  If you can, what do you want to have happen in this case?  Do you want both $S[A]$ and $S[A \cup B]$ (and $\operatorname{mex} A$ and $\operatorname{mex} B$) to be updated rapidly?  
> **username_0**: @username_1 - We can assume that we could do that. It just boils down to creating $S[\{a\}]$ for each element in $A$, and then taking the union of all these.  
> **username_0**: @username_3 - no, for my use case, set modifications are not allowed, we may assume that $S[A]$ is effectively immutable after creation.  
> **username_0**: @username_2 - Looking just at the abstract, this may be exactly what I need!  
> **username_0**: @username_2 - the paper you referenced is quite nice, and it discusses supporting predecessor with union in $O(\log n)$ amortized. But I don't see how from these we could compute the minimal excludant.  
> **username_2**: @username_0 - The merge process described in section 2.1 shows the merge operation finds the min/max of each segment. You can use this information to calculate $mex$ at the same time during each merge. The $O(\log^2)$ amortized bound still holds.  
> **username_0**: @username_2 - In section 2.1, the notion of a segment S of the operation $\mbox{merge}(A, B)$ does not imply that this segment doesn't contain gaps (which are candidates for the mex of the union). For example, for $A = \{1,3,4\}, B = \{4, 5, 6\},$ then $C = \{1,3\}$ is a segment for $\mbox{merge}(A, B),$ but only by knowing its endpoints is not sufficient to check for the numbers which are not inside it (e.a. 2).  
> **username_0**: By thinking about this problem a little bit more, it can be restated as follows: maintain a dynamic collection $\{A_1, A_2, ...\}$ of subsets of ordered universe $U,$ with respect to finding the minimal element of $A_i,$ and finding the intersection of two existing sets (then maybe removing them from collection, and of course, after this operation, C becomes part of the collection and it becomes possible to intersect it with other sets from the collection): $C = A_i \cap A_j.$  
> **username_2**: I see I misinterpreted the definition of the segment. I don't see a obvious solution to this. I wonder if it's possible to argument the DS to return the size of a set in $O(\log n)$ amortized time.  
> **username_1**: Can some natural number $x$ be in both $S[A]$ and $S[B]$? The analysis in Iacono and Özkan's paper does not apply, if so, I believe.  
> **username_2**: Is there an application of this data structure you are thinking of? I thought this was useful for combinatorial game theory, but I can't think games where it's faster to union sets and find mex than just directly maintain a set and find mex.  

---

## 1 answers

### Answer by username_4 on 2015-12-21. Score: 4 | Accepted answer

Here are two solutions which (as suggested in the question and comments) assume that all the given sets are disjoint and performs destructive set unions (when we find the union of sets A and B, we remove A and B themselves from the family of sets).

**Amortized constant time**

We maintain objects for the sets and objects for the elements. The sets know what elements they have, as a concatenable list, so that we can list those elements quickly, but we don't keep pointers from the objects to the sets that contain them (because it would be too slow to update them).

There is at most one special set Z, the one containing zero. Every object knows whether it is part of Z or not (a binary flag). The set Z maintains the value of its mex. For every other set, the mex is zero. So you can compute the mex of a set in constant time, given either the set itself or one of its elements.

To form the union of two sets, if neither one is Z, just concatenate their lists. If one of the two sets is Z, run through its elements setting the flag that says the element is now in Z. Then, while the mex is an element of Z, increment it.

Each element accounts for one increment operation to the mex of Z, so the amortized time per element, merge, or mex request is constant.

**Worst-case logarithmic time**

For a worst-case rather than amortized (but slower) solution, that also allows for creation of new singleton sets and does not assume that the union of all the sets is a contiguous interval, we use the following data structures:

* union-find rather than flags to determine the set that contains any element (even if we just do union-by-rank without path compression, this is worst-case logarithmic per find operation)
* a binary search tree of the elements in the union of all the sets
* for each element, the smallest non-element between it and its predecessor in the binary search tree (or zero if it has no predecessor)
* for each binary search tree node, the smallest non-element listed in its subtree (updated in constant time per tree rotation)
* the smallest element of each set
* a priority queue of the smallest elements of sets that are not Z.

Then at all times mex(Z) is the minimum of the priority queue value and the smallest non-element. And as before, for sets that are not Z, the mex is zero. Adding a new singleton set, merging two sets, or finding a mex all take logarithmic time with more-or-less obvious updates.


---

