Sum to zero of all triples in a list - n^2 running time As part of an interview, I had to submit a code sample to solve the classical "triples sum to 0" problem. The reviewer said the algorithm needed to be in n2 time, and I was later informed that the code I wrote did not accomplish this.

Can you guys help me identify where I went wrong? I've written comments explaining my thought process.

# Small struct to hold the values we need for computing unique sums
DoubleSum = namedtuple('DoubleSum', 'arg_sum int1 int2 int1_index int2_index')


def sum_zero(integers: [int]) -&gt; [(int, int, int)]:
    """
    Given a list of integers, compute all triples that sum to 0
    :param integers: The integers to arrange
    :return: All triples that sum to 0, or [] if there are no sums
    """
    # Check for trivial issues
    if integers is None or len(integers) &lt; 3:
        raise ValueError("Must have an input of at least 3 integers to check.")

    s_integers = sorted(integers)

    # Compute all unique possible sums of two integers
    # Should run in n^2
    sums = []
    for i in range(0, len(s_integers)):
        for j in range(i+1, len(s_integers)):
            int1 = s_integers[i]
            int2 = s_integers[j]
            sums.append(DoubleSum(int1+int2, int1, int2, i, j))

    # For each integer, find all two-element sums that would equal 0
    # Should be n^2 - for each integer, find all double sums that match it
    triples = []
    for i in range(0, len(s_integers)):
        current = s_integers[i]
        matches = filter(lambda s: s.arg_sum == -current, sums)
        for match in matches:
            test_triple = (i, match.int1_index, match.int2_index)
            # If the current index isn't below both indices in the sum,
            # we have come across another permutation of a previous sum to 0
            if i &lt; match.int1_index and i &lt; match.int2_index:
                triples.append(test_triple)

            # We could reduce the runtime if we added a break statement to the
            # else clause, but that seems to introduce errors after maintenance
            # when nobody quite remembers what the break did in the first place

    # Map the indices in `triples` to the actual values
    return [(s_integers[t[0]],
             s_integers[t[1]],
             s_integers[t[2]]) for t in triples]
Your first pair of loops builds the list sums. The length of this list is \$O(n^2)\$ in the length of the input.

In your second set of loops for each element in s_integers you filter all of sums to find those elements which match it. The runtime of this filter process is linear in the length of sums, and hence quadratic in the length of the input. You perform this quadratic process once for each member of the input list; the search loop is therefore cubic in the length of the input.

Your algorithm as a whole is therefore \$O(n^3)\$ in the length of the input.

To make the algorithm as a whole quadratic, you need to make the second (match) stage linear in the length of sums. Natural approaches would include:


Using a dictionary or some other map structure to lookup elements in the original either s_integers or sums by magnitude, in constant time; the match stage is then linear in the length of the other list. (Probably fastest on real input; it might be slightly tricky to check that there are no pathological cases, depending on which list you do lookup on).
Sorting sums (\$O(n \log n)\$), then effectively 'merging' sums and s_integers, (\$O(n)\$ in the length of the larger). This is easiest to prove to be \$O(n^2)\$