Two problem related to sequence of sets

Solve the problem by building a trie over the lexicographic ordering of the elements in the set. Since the alphabet has size $n$, it has running time $O(m\log n)$. One can get better running time using integer data structures, say $O(m\log \log n)$ using van Emde Boas tree.

$O(m)$ time is actually possible. For each $k$, we build the set $H_k=\left\{j|k\in S_j\right\}$ (as a list). We define equivalent relation ${\equiv }_k$ as $i{\equiv }_{k}j$ if $S_i\cap [k]=S_j\cap [k]$. If we have equivalent class of ${\equiv }_k$, we can obtain the equivalent class of ${\equiv }_{k+1}$ in $O(|H_k|)$ time. Hence together the running time is $O(m)$.

We assume the elements in the sets are in $[m]$. Let $S={\bigcup }_{i=1}^n{S}_i$.

For $k=0,1$, we can solve it in $O(m)$ time: Decide if any element appears more than once in the sets.

For larger $k$, we shall compute $|S_i\cap S_j|$ for every pair $i$ and $j$. To do this, we start with an all zero $n\times n$ matrix $C$. At the end of the algorithm, $C_{i,j}=|S_i\cap S_j|$ for all $i,j\in [n]$. For each element $x$, we find $E_x=\left\{i|x\in S_i\right\}$. This takes $O(m)$ time. We increment $C_{i,j}$ for all $i,j\in E_x$. We claim this algorithm have running time $O(nm)$. Indeed, for each $x$, we spend $|E_x|$ time in incrementing $C_{i,j}$ where $i,j\in E_x$. Hence the running time is bounded by ${\sum }_{x\in S}|E_x{|}^2$. We know ${\sum }_{x\in S}|E_x|=m$ and $|E_x|\le n$. We see the worst case is when $|E_x|=n$ and $|S|=m/n$. In that case, we have running time $O({\sum }_{x\in S}{n}^2)=O(mn)$.

Since we just want to find a pair $\left\{i,j\right\}$ where $|S_i\cap S_j|\ge k$. We can stop the algorithm as soon as $C_{i,j}\ge k$ for some $i$ and $j$. This means we can increment at most $(k-1)n^2$ times.

Together, the running time become $O(\min (nm,k{n}^2+m))$.

For $k=2$. One can improve the running time when $n$ is large by reduce it to a problem similar to finding rectangles or finding a $C_4$ in the incident graph. Let $n^{\prime }$ be $|{\bigcup }_i{S}_i|$, we can obtain a more refined bound. Together, the final running time for $k=2$ is $O(\min (m^{4/3},dm,n^2+m))$. Here $d$ is the degeneracy of the incident graph of the sets and the elements, which is bounded above by the maximum degree.

Recently, I had some result for $k=3$, where the running time improves to $O(m^{28/15})$.