1
$\begingroup$

Suppose I want to find the numbers that appear in at least 3 of the 10 sorted lists, is there an efficient way to do it apart from iterating over all 10 of them in parallel?

$\endgroup$
2
$\begingroup$

The simplest way is to first remove duplicates from the 10 lists, and then merge all of them. Any number appearing 3 times in the merged list also appears in 3 of the 10 sorted lists.

A more complicated way is using pointers as you indicate. Briefly, the pointers start at the beginning of the lists, and then you keep incrementing the pointer pointing at the minimal element. You can use a heap to implement detecting which pointer to advance.

If you have $m$ lists containing $n$ elements in total, the first way takes optimal time $O(n)$ but uses up space (or modifies the input), and the second takes time $O(n\log m)$ (the $\log m$ comes from the heap) but uses less auxiliary space.

$\endgroup$
  • $\begingroup$ What if the original sorted lists are skip lists? Is there something else we can do? $\endgroup$ – Gabizon Jul 30 '17 at 21:30
  • $\begingroup$ I doubt it, but you're welcome to try. $\endgroup$ – Yuval Filmus Jul 30 '17 at 21:30
1
$\begingroup$

You could consider using a hash table.

Just store each number together with three element array that holds information about which array that integer belongs to (pointer to the list for example). Every time you add an element to the hash table, check if its three element array is full, meaning that element is in at least three lists, and so add that integer to another array which holds desired elements so that not to scan the hash table again. This will take $O(n)$ time where $n$ is the total number elements.

In addition, if your integers are bounded by $K$ then you could simply use an array of size $K$ as the hash table.

$\endgroup$
0
$\begingroup$

There's a method I found some time ago that works if you have iterators that can "forward" to or past a given value easily, eg with a skip list, in addition to the usual "next", ie it can do the equivalent of multiple next's to reach a given value, with sublinear cost. (I'll refer to these iterators below as single values X for the purposes of which one is minimum etc. at any given time.)

If you want runs of length $k$, do replacement selection (the heap-of-iterators idea), but pipe the heap into a FIFO/ring buffer of length $k-1$. Picture this as a funnel, where the sharp end of the heap goes into a fixed-length FIFO, and we iteratively pull the minimum off the end of the FIFO and reinsert it after bumping it forward as I'll describe.

To bump the smallest element E on the FIFO, compare it with the minimal element M on the heap. If E = M, we have a run, so output E's value, move it to its next value, and put it back on the heap while moving M to the FIFO. If E < M, forward it to or past M, move M to the FIFO, and put E back on the heap. Note we don't insert the bumped value into the FIFO; that's the fun part.

The FIFO in this case is an obvious way to see runs in the merged sequence, but it also allows us to forward E past runs which will never reach length $k$. The reason is that if E and M are different, then any value X between them in the FIFO can never reach $k$ repetitions, even if E and everything to the left of X comes to equal X eventually. That is, if the FIFO and M contain

$E...X,...X,..M$

it can possibly become, if E.next = X, say,

$X...X,..M$,

but never the case where all $k$ are

$X..X$

by simple counting.

So we can forward E's value past any $X$ where $E < X < M$ without losing any k-runs.

$\endgroup$
  • $\begingroup$ Can you estimate the time complexity of this procedure? $\endgroup$ – Yuval Filmus Jul 31 '17 at 8:21
  • $\begingroup$ I'll see what I can do. $\endgroup$ – KWillets Jul 31 '17 at 16:12

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.