data-structures · advanced · ~40 min
The sort + two-pointer pattern that turns O(n^3) into O(n^2).
Given int *a, size_t n, return the number of unordered triples (i<j<k) with a[i]+a[j]+a[k] == 0. Implement size_t count_3sum_zero(int *a, size_t n). You may modify a.
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.
Array of n ints (n <= 1000). Values fit in int.
The count as size_t.
Sorting + two-pointer; O(n^2).
#include <stddef.h>
size_t count_3sum_zero(int *a, size_t n) { /* TODO */ return 0; }
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).
n<3 returns 0. All zeros: C(n,3) triples. No solution.
O(n log n) sort + O(n^2) two-pointer = O(n^2).
Solve this exercise in the browser editor — compile and run against the test harness, no setup required.