3Sum

/*
Logic:sort the array first and then one loop on whole array for one elemnt of triplet and other two element will be found by two-pointer.
*/

class Solution:
    def threeSum(self, arr: List[int]) -> List[List[int]]:
        arr.sort()
        ans=set()
        for k in range(len(arr)):
            if k > 0 and arr[k] == arr[k-1]:   # skip duplicate k
                continue

            i,j=k+1,len(arr)-1
            while i<j: #no need to check i!=k or j!=k because i start after k and i never gonna reach j
                # i+=1 if k==i else j-=1
                if arr[k]+arr[i]+arr[j]==0:
                    t=(arr[k],arr[i],arr[j])# (k,i,j) always increasing bcz k come first then i & j as pointer on both side
                    ans.add(t)
                    i+=1
                    j-=1

                    while i < j and arr[i] == arr[i-1]:   # skip duplicate i
                        i += 1
                    while i < j and arr[j] == arr[j+1]:   # skip duplicate j
                        j -= 1

                elif arr[k]+arr[i]+arr[j]>0:
                    j-=1
                else:
                    i+=1

        return [list(x) for x in ans]