I’m pretty sure the space complexity here would be O(n), because we are creating a new Python list as the return variable.
Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: Solution: Merge Intervals - Grokking Coding Interview Patterns in Python
Thank you for reaching out to us with your query. Regarding the space complexity in the Merge Intervals problem, we do not consider the space acquired by the input and output data structures in the overall space complexity of the solution function. The reason for doing this is that space complexity is used to compare the efficiency of two different solutions to the same problem. The space acquired by the input and output data structures will remain the same, regardless of the solution we use. Hence, it is not considered in the space complexity of the solution function. As for the Merge Intervals problem, the space acquired by the result list is to store the output of the function, therefore, it is not included in the space complexity of the solution function.
I hope this clarifies your confusion. If you still have any questions, please feel free to ask us.