About the space complexity storing all subarrays

The article asks “Can you try estimating how much space will be required for the output list?”
The answer it gives is O(N^2).

The average length of a subarray is O(N), and there’re O(N^2) subarrays in total, so the space complexity for storing all subarrays should be O(N^3).

Please correct me if I’m wrong.

1 Like

I agree, the space complexity is O(N^3). The article is only counting the subarrays without taking their length into account.

1 Like

Yes, I had the same concern. The space complexity should be O(N^3)