# LeetCode 15 – 3Sum

#### Posted on December 25, 2013

##### Last updated on December 25, 2013

Solution to LeetCode 3Sum problem.

Naive way is $$O(n^3)$$ – look at all triplets. We can improve this to $$O(n^2)$$ by first sorting the array, and traversing it with three pointers $$0 \leq i \lt j \lt k \lt N$$. For every choice of $$i$$, use the 2SUM algorithm on the sorted subarray, and find $$j$$,$$k$$ such that $$A(j) + A(k) = C - A(i)$$, where in this question variant $$C = 0$$. We must take care to not print duplicate elements.

Markdown SHA1: 599dee13a7ee0d66e6e6e34d2f01f2684873857f