Hacker News Reader

Comment by bjornsing | Hacker News Reader

If the “lists” are not random access, and you know their lengths, then why not just traverse them in parallel? I find it hard to believe you can do it faster than that, and it’s super simple...

View on HN

What do you mean by "traverse them in parallel"? You want to find the medians of the two lists independently and then somehow combine them? How?

You have two indices, one for each list, updated separately. Iterate through a lost until it’s next element is larger than the current element in the other list. Iterate through it until the same condition. Keep going until your present position is at the halfway point, the you’ve got your median.

They don’t mean parallel like two thread, though you could use two coroutines or a similar mechanism.

Thanks. That makes sense. The "in parallel" certainly threw me off.

Although in the article the author at some point switches from lists to vectors, which changes the whole task, and allows for a more efficient implementation (even if it's an answer to a different question).

traversing them won't get you O(log(m+n)) complexity.

If they truly are lists (i.e. not random access) then nothing will give you that. If you have the head elements of the lists and you want the median then you have to traverse (m+n)/2 elements just to get to the median. There is no way around that. If you translate the lists to arrays then that’s an o(n+m) operation in itself.

ah yes, of course, that was a misreading on my part, sorry. the title is somewhat misleading, but if you go have a look at the original problem you see that it provides as inputs random-access arrays, not linked lists. i only changed them to lists in the initial, naïve solution in order to keep things simple at first.

Reply on news.ycombinator.com