Leetcode 15. 3Sum

Problem

Leetcode 15 - 3Sum

Example:

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.

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

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Approach

We can first sort the array, then look for two sum for each nums[i]

• if nums[i] > 0, we have to break since all the elemnts on the right side will be bigger
• if i > 0 and nums[i] == nums[i-1], we continue since no duplicates

Then we can apply two sum

Since we’re trying to get a target with sorted array, we can simply use two pointer one at beginning of the array, and one at the end of the array. There are 3 outcomes of these sums

• sum < target:
  • we increment left pointer
• sum > target:
  • we decrement right pointer
• sum == target:
  • we simply return index of two pointer

Here is the Python code for the solution:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        res = []

        for i, a in enumerate(nums):
            if a > 0:
                break
            if i > 0 and a == nums[i-1]:
                continue

            left, right = i+1, len(nums)-1
            while left < right:
                threeSum = a + nums[left] + nums[right]

                if threeSum < 0:
                    left += 1
                elif threeSum > 0:
                    right -= 1
                else:
                    res.append([a, nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left-1]:
                        left += 1
        
        return res

Time Complexity and Space Complexity

Time Complexity: $O(n^2)$

Space Complexity: $O(1)$