Skip to content

Dsa Two Pointers 3Sum

DodaTech 1 min read

In this tutorial, you'll learn about How to Fix 3Sum Errors. We cover key concepts, practical examples, and best practices.

Fix 3sum errors when skip duplicates condition wrong or outer loop doesn't terminate.

Quick Fix

Wrong

def three(a):
    a.sort(); n=len(a); res=[]
    for i in range(n-2):
        if i>0 and a[i]==a[i-1]: continue
        l=i+1; r=n-1
        while l<r:
            s=a[i]+a[l]+a[r]
            if s==0:
                res.append([a[i],a[l],a[r]])
                l+=1; r-=1
                while l<r and a[l]==a[l-1]: l+=1
                while l<r and a[r]==a[r+1]: r-=1
            elif s<0: l+=1
            else: r-=1
    return res

Correct version. Common bugs: not skipping outer i duplicates, inner skip logic off-by-one.

def three(a):
    a.sort(); n=len(a); res=[]
    for i in range(n-2):
        if i>0 and a[i]==a[i-1]: continue
        l=i+1; r=n-1
        while l<r:
            s=a[i]+a[l]+a[r]
            if s==0:
                res.append([a[i],a[l],a[r]])
                l+=1; r-=1
                while l<r and a[l]==a[l-1]: l+=1
                while l<r and a[r]==a[r+1]: r-=1
            elif s<0: l+=1
            else: r-=1
    return res

[-1,0,1,2,-1,-4] -> [[-1,-1,2],[-1,0,1]]. O(n^2).

Prevention

Sort, fix first element, two-pointer for remaining. Skip duplicates at outer and inner loops.

DodaTech Tools

Doda Browser's algorithm visualizer steps through DSA operations line by line. DodaZIP archives implementation patterns for team sharing. Durga Antivirus Pro detects memory corruption patterns in algorithm implementations.

FAQ

What is 3Sum?

All triplets summing to zero. O(n^2) with sorting + two pointers.

Skip duplicates?

Skip outer: if a[i]==a[i-1]. Skip inner: after finding solution, skip same l/r.

Optimization?

Prune: if a[i]+a[i+1]+a[i+2]>0 break. If a[i]+a[n-1]+a[n-2]<0 continue.

← Previous Dsa Trie Word Break Next → Dsa Two Pointers Remove Dups

Built by the developers of DodaTech

Doda Browser, DodaZIP & Durga Antivirus Pro

Home Browse Quick Fix