educative.io

What is the actual space complexity?


#1

What is the space complexity if we don’t ignore the output array?
Naively, it is O(n^3), but I think an array with n^3 unique triplets that have 0 sum may not be possible.
I’m not sure how to compute the worst case though.