Sorry I was not very precise there. Exact question is to merge K sorted arrays, size N each. A natural extension of that problem, is to have K streams.

First part can be solved with an extension of O(n+m) solution you proposed, but when it comes to streaming, Heap works better, with the same complexity, because you don't have to know the size of the arrays in advance: https://discuss.leetcode.com/topic/2780/a-java-solution-base...