3SUM: triples summing to zero

Challenge

Count the distinct value-triples in an array that sum to zero.

Task

Given an array a of n ints, implement size_t count_3sum_zero(int *a, size_t n) that returns how many distinct triples of values (x, y, z) drawn from a (using three different positions) satisfy x + y + z == 0. Triples are de-duplicated by value, so {0,0,0} counts once no matter how many zeros there are. You may modify a (e.g. sort it).

Input

• a: writable array of n ints (n <= 1000); values fit in int.
• n: the number of elements.

Output

size_t: the number of distinct zero-summing value-triples.

Example

{-1,0,1,2,-1,-4}   ->   2     ({-1,-1,2} and {-1,0,1})
{0,0,0,0}          ->   1     (the {0,0,0} triple, counted once)
{1,2,3}            ->   0

Edge cases

• n < 3 returns 0.
• Repeated values must not produce duplicate triples.

Rules

• Target O(n^2): sort, then use the two-pointer sweep. Use a wide type (long) when summing to avoid overflow.

Why this matters

3SUM is a foundational problem in computational geometry, finance signal detection, and is the basis for many O(n^2) lower-bound reductions in algorithms research.

Input format

a: writable array of n ints (n <= 1000); n. Values fit in int.

Output format

size_t: count of distinct value-triples summing to zero.

Constraints

Sorting + two-pointer; O(n^2). De-duplicate triples by value.

Starter code

#include <stddef.h>
size_t count_3sum_zero(int *a, size_t n) { /* TODO */ return 0; }

Common mistakes

Double-counting because the loop didn't skip duplicates; off-by-one in the inner pointer convergence; integer overflow when summing 3 INT_MAX values (use long).

Edge cases to handle

n<3 returns 0. All zeros: C(n,3) triples. No solution.

Complexity

O(n log n) sort + O(n^2) two-pointer = O(n^2).

Background lessons

• The two-pointer technique
• Sorting overview