Yes, we will need O(N+M) space for the result list.

Do you guys have an example input that can achieve the worst case space complexity?

Any two lists where all intervals don't overlap will need O(N+M) space. With such an input, there won't be any merging and all intervals from the input lists will end up in the result list, giving us O(N+M) space complexity.

But shouldn't the result list only contain intervals that intersect? If there is no overlap at all, the resulting list will be empty. The only other possible worst case I could think of is if there is complete overlap between the two input lists which leads to O(n) or O...

You are right about the interval intersection, our last comment is not valid.

We will have O(M+N) space complexity for input like this:

Input lists: [[0,2],[5,10],[12,23],[24,25]] [[1,5],[8,12],[15,24],[25,26]]

Output: [[1,2],[5,5],[8,10],[12,12],[15,23],[24,24],[25,...