Four Sum

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

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

Pseudocode

sort array
fix i, j (two nested loops)
two-pointer the rest for sum = target - a[i] - a[j]

Reference implementation

for i in range(n-3):
    for j in range(i+1, n-2):
        lo, hi = j+1, n-1
        while lo &lt; hi:
            s = a[i]+a[j]+a[lo]+a[hi]
            if s == target: out.append((...)); lo+=1; hi-=1
            elif s &lt; target: lo += 1
            else: hi -= 1

Open the interactive Four Sum visualisation →