Three Sum

An interactive, step-by-step visualisation of Three Sum.

Category: Two Pointers
Time complexity: O(n²)
Space complexity: O(1)

Pseudocode

sort array
for each i: two-pointer the rest for sum = -a[i]
skip duplicate i, lo, hi values

Reference implementation

a.sort()
for i in range(len(a) - 2):
    if i &gt; 0 and a[i] == a[i-1]: continue
    lo, hi = i+1, len(a)-1
    while lo &lt; hi:
        s = a[i]+a[lo]+a[hi]
        if s == 0: out.append((a[i],a[lo],a[hi])); lo+=1; hi-=1
        elif s &lt; 0: lo += 1
        else: hi -= 1

Open the interactive Three Sum visualisation →