"Three sums" problem space complexity - Why is it O(n)?

Question

Leetcode - Three sums

https://leetcode.com/problems/3sum/

def threeNumberSum(array, targetSum):
    array = sorted(array)
    results = []
    for idx, elem in enumerate(array):
        i = idx + 1
        j = len(array) - 1
        target = targetSum - elem
        while i < j:
            currentSum = array[i] + array[j]
            if currentSum == target:
                result = [array[i], array[j], array[idx]]
                results.append(sorted(result))
                i += 1 
                j -= 1 
            elif currentSum < target:
                i += 1
            else:
                j -= 1

    return results  

So time is O(n^2), I am fine with that, but space is O(n), according to Algoexpert.io, and I am not sure of why. His explanation was:

"We might end up storing every single number in our array, if every single number is used in some triplet, we will store a lot of numbers and it is going to be bound by O(n) space. Even if some numbers are used multiple times, it will be bounded by O(n)"

But I can't make sense of his explanation yet. If the provided array has (nearly) all unique triplet permutations summing to that target number, isn't space complexity going to be n choose 3 instead? If its n choose k=3 simplifying it would yield O(n^3).

Note, however, that the Algoexpert problem has one additional assumption with the input array that every element will be distinct, whereas the Leetcode version doesn't have that assumption. How would I formally address that information in space complexity analysis?

Answer 1

If your code is correct (and I have no reason to assume it isn't), then the space complexity for the list of matching triplets is in fact O(n²).

It's not O(n³) because the third member of any triplet is uniquely determined by the first two, so there is no freedom of choice for this value.

If all the numbers are unique, then the space requirement is definitely O(n²):

>>> [len(threeNumberSum(range(-i,i+1),0)) for i in range(1,10)]
[1, 2, 5, 8, 13, 18, 25, 32, 41]

You should be able to satisfy yourself that the terms in this series correspond to ceil(n²/2). (See https://oeis.org/A000982).

If there are repeated numbers in the list, then the overall space requirement should decrease (relative to n) due to the requirement for unique triplets in the returned array.