0015. 3Sum

Medium | Math + Hash Table | 624 ms (97.81%), 17.8 MB (32.19%)

❓ Problem Statement

Source: LeetCode - 3Sum GitHub: Solution / Performance

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.

✍🏻 Constraints & Example

Constraints:

• 0 <= nums.length <= 3000

• -10^5 <= nums[i] <= 10^5

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

Input: nums = []
Output: []

Input: nums = [0]
Output: []

💡 Ideas

Same idea as 0001. Two Sum with more case handlings.

There are several different cases for the sum of three numbers that equal ZERO.

• 0, 0, 0

• -n, 0, n

• -n, -m, m+n

• -n-m, n, m

We need to use a specific data structure (Set in Python) to solve this problem with an extra constraint that the solution set must not contain duplicate triplets.

We store negative numbers, ZERO, positive numbers into a list and a set separately. Then, we use the numbers stored in the list to calculate the remaining value and then search it in the Set. Once we find it, we add it to the other Set as the final answer.

🤖 Python3

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # (base case)
        if len(nums)  < 3: return []
        if len(nums) == 3: return [nums] if sum(nums) == 0 else []
        
        # ==================================================
        #  Math + Set                                      =
        # ==================================================
        # time  : O(n^2)
        # space : O(n) 
        
        zero, negative, positive = [], [], []
        for num in nums:
            if num > 0: positive.append(num)
            elif num < 0: negative.append(num)
            else: zero.append(num)
                
        # (case handling)
        if len(negative) == 0:
            if len(zero) == 0: return []
            if len(positive) == 0 and len(zero) < 3: return []
            if len(positive) == 0 and len(zero) == 3: return [[0, 0, 0]]
        
        ans = set()
        negSet = set(negative)
        posSet = set(positive)
        
        if len(zero) > 2: ans.add((0, 0, 0))
        
        # (-n, n, 0)
        if zero:
            for num in negSet:
                if -num in posSet: ans.add((num, -num, 0))
        
        # (-n, -m, n+m)
        for i in range(len(negative)):
            for j in range(i+1, len(negative)):
                remain = -1 * (negative[i] + negative[j])
                if remain in posSet: ans.add(tuple(sorted([negative[i], negative[j], remain])))
        
        # (n, m, -n-m)
        for i in range(len(positive)):
            for j in range(i+1, len(positive)):
                remain = -1 * (positive[i] + positive[j])
                if remain in negSet: ans.add(tuple(sorted([positive[i], positive[j], remain])))
                    
        return ans