15. 3Sum - Leet Code

Problem Description

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

• Input: nums = [-1,0,1,2,-1,-4]

• Output: [[-1,-1,2],[-1,0,1]]

• Explanation:

  nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.

  nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.

  nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.

  The distinct triplets are [-1,0,1] and [-1,-1,2].

  Notice that the order of the output and the order of the triplets does not matter.

Example 2:

• Input: nums = [0,1,1]
• Output: []
• Explanation: The only possible triplet does not sum up to 0.

My Idea

First we sort the list to allow the simple use of pointers. Then we iterate over the list and for each element we create two pointers that examine the rest of the list from both ends, checking if the 3sum is =0 and reacting accordingly. This approach would not be so simple if the list wasn’t sorted, since it wouldn’t be clear which pointer to move and in which direction.

My solution

# Time Complexity: O(n^2)
def threeSum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    res=[]
    for i in range(0,len(nums)-2):
        if i>0 and nums[i]==nums[i-1]:
            continue
        left = i+1
        right = len(nums)-1
        while left<right:
            if nums[i]+nums[left]+nums[right]==0:
                res.append([nums[i],nums[left],nums[right]])
                while left<right and nums[left]==nums[left+1]:
                    left+=1
                while left<right and nums[right]==nums[right-1]:
                    right-=1
                left+=1
                right-=1
            elif nums[i]+nums[left]+nums[right]<0:
                left+=1
            else:
                right-=1
    return res