educative.io

Educative

Why is the space complexity O(N) for this solution?

When populating the min_heap, the given solution stores the list in the min_heap. Why should this list count towards additional space complexity, given that it is simply a reference to the list that’s being stored on the heap and not the list itself?

@Abhimanyu_Sahai, basically, we are storing our lists in a heap, so in the worst scenario, its space complexity might be O(n). As mentioned in the explanation we store one element from each list in the min-heap, along with the entire list itself.