Problem Statement in English

You’re given an integer array nums. Your task is to find all unique triplets in the array which gives the sum of zero.

Approach

This builds on a problem we’ve done before. Except here we have an outer loop that considers every possible number, and a nested loop that controls the 2 pointers, operating on all numbers to the right of the index being considered by the outer loop.

Solution in Python


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = []
        
        # sort the array
        # we need this for the 2 pointer technique
        nums.sort()

        # -2 because we want iterate until the third last element
        for a in range(len(nums) - 2):
            if a > 0 and nums[a] == nums[a - 1]:
                # ensure that the pointer points to something new,
                # when compared to the last index
                # if not, skip this index
                continue

            l, r = a + 1, len(nums) - 1

            # if all pointers point to elements > 0,
            # then no more triplets exist,
            # since we need atleast one -ve number in such a case!
            # and so, we can stop looking for more triplets altogether
            if nums[a] > 0 and nums[l] > 0 and nums[r] > 0:
                break

            while l < r:
                # otherwise proceed to calculate current 3 sum,
                # and evaluate it
                s = nums[a] + nums[l] + nums[r]

                # if the sum's too big, reduce it
                if s > 0:
                    # move `r` left
                    r -= 1

                    # ensure that r points to a distinct number
                    # and `l` < `r`
                    while nums[r] == nums[r + 1] and l < r:
                        # skip this index
                        r -= 1
                else:
                    # it's a valid 3 sum
                    if s == 0:
                        # add it to `ans`
                        ans.append([nums[a], nums[l], nums[r]])
                        # now, either move l or r
                        # i chose to move l

                    # move `l` right
                    l += 1

                    # ensure that l points to a distinct number
                    # and `l` < `r`
                    while nums[l] == nums[l - 1] and l < r:
                        # skip this index
                        l += 1

        # return `ans`
        return list(ans)

Complexity

  • Time: $O(n^2)$
    Since we use a nested loop.

  • Space: $O(1)$
    Since we only use a couple integer pointers.

Mistakes I Made

I had to look this one up :(

And we are done.