Find the median of a list of sorted arrays
You can do it in $O(l + k \text{ log } l)$ time and $O(l)$ extra space as follows:


Build a binary heap with one entry for each of the arrays.  The key for entry $i$ is the smallest element in array $A_i$.  This takes $O(l)$ time.
Select the smallest entry from the heap and remove it (taking $O(\text{log } l$) time).  Add that entry back to the heap using the next smallest entry in the relevant array as its key (again $O(\text{log } l)$ time).
Do the previous step $k$ times.  The last element you remove from the heap is your answer.


If you replace the binary heap with a Fibonacci heap, I think this gets you down to amortized $O(l + k)$ time, but in practice it'll be slower than the binary heap unless $l$ is HUGE.

I suspect that the Fibonacci heap bound is optimal, because intuitively you're going to have to inspect at least $k$ elements to find the $k$th smallest one, and you're going to have to inspect at least one element from each of the $l$ arrays since you don't know how they're sorted, which immediately gives a lower bound of $\Omega(\text{max}(k, l)) = \Omega(k + l)$.