> e.g. If they ask you to merge sorted arrays and you don't know that Heap sort is the best way to do it
Sorry, I'm confused. I love heaps, but... what's wrong with this simple O(n+m) time and space solution, that I can easily prove is the theoretical limit (because the output size is O(n+m))?
def merge_sorted(a, b):
result = []
la, lb = len(a), len(b)
ia, ib = 0, 0
while ia < la or ib < lb:
if ib >= lb:
result += a[ia:]
break
if ia >= la:
result += b[ib:]
break
if a[ia] <= b[ib]:
result.append(a[ia])
ia += 1
else:
result.append(b[ib])
ib += 1
return result
assert merge_sorted([], []) == []
assert merge_sorted([1, 2, 3], []) == [1, 2, 3]
assert merge_sorted([], [1, 2, 3]) == [1, 2, 3]
assert merge_sorted([1, 3, 5], [2, 4]) == [1, 2, 3, 4, 5]
assert merge_sorted([2, 4], [1, 3, 5]) == [1, 2, 3, 4, 5]
assert merge_sorted([1, 2, 3], [1, 2, 3]) == [1, 1, 2, 2, 3, 3]
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...
Sorry, I'm confused. I love heaps, but... what's wrong with this simple O(n+m) time and space solution, that I can easily prove is the theoretical limit (because the output size is O(n+m))?