Given a collection of sets $C= \{S_1,S_2,\cdots,S_n\}$ such that each set $S_i \in C$ is sorted and has at least $k$ elements.

What is the most efficient algorithm for finding the intersection of these sets: $\bigcap_{S_i \in C}{S_i}$

  • $\begingroup$ @Raphael I tried having a universal set that contains all elements in the sets, then iterate these elements and check their existence in $S_i$. I am looking for a better algorithm. $\endgroup$ – M.M Jun 15 '15 at 12:19
  • $\begingroup$ Related question. $\endgroup$ – Raphael Jun 15 '15 at 12:55

If the least elements in all $S_i$ are equal then pick it for final set else pick least element among all $S_i$ and remove (remove minimum among all sets and not minimums of all sets). This works in $O(n*|C|*log |C|)$, where $|C|$ is the total number of elements in $C$ (not it's cardinality). This works since all your $Si$ are sorted and removal of element will maintain the sorted order.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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