[Leetcode][python] 15. 3Sum

problem:

 

code:

#Input: nums = [-1,0,1,2,-1,-4]
# currentArray : -1, 0
# resultArray : [-1, 0, 1]

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        result = []
        def checkExists(num1, num2, num3):
            for items in result:
                if (num1 in items) and (num2 in items) and (num3 in items):
                    return True
            return False
        
        #traversal num
        allZeroFlag = False
        for i in range(len(nums)): # N
            for j in range(i+1, len(nums)): # N-1
                for k in range(j+1, len(nums)): # N-2
                    #check sum of 3 values 
                    if nums[i]+nums[j]+nums[k] == 0 :
                        if nums[i]==0 and nums[j]==0 and nums[k]==0 :
                            allZeroFlag = True
                            continue
                        # check if it already exist 
                        if checkExists(nums[i],nums[j],nums[k]) == False :
                            result.append([nums[i],nums[j],nums[k]])
        if allZeroFlag :
            result.append([0,0,0])
            
        return result
        
'''
Example
Input: nums = ['-1','0','1',2,-1,-4]
find 3 values which meet below conditions
 
1. recursiveFunction -> short and simple code
2. for loop -> easy to understand

Time complexity
    O(N^3) 
    to exactly N*(N-1)*(N-2)
    
Space complexity -> ?
    O(N)

'''

 

 

Additional opinion 1.

In the 'checkExists' function, I first code below this way.

#if (num1 in items) and (num2 in items) and (num3 in items):
                    #return True

 

But If I do this ways, there is edge case : (0,0,0)

 

So I failed it

So I added flag 'allZeroFlag' which marks all 3 of values are 0.

But I got time limited exceeded.....

 

 

 

Additional opinion 2.

But the time complexity of my code is N^3.

So I need to optimize it.

If I sort the nums array and traversal the array only two times similiar to 'binary search tree' ,

it will take less time than before.

 

 

better code:

TC = O(logN*N^2)

#Input: nums = [-1,0,1,2,-1,-4]
# currentArray : -1, 0
# resultArray : [-1, 0, 1]

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        left = 0
        for left in range(len(nums)-2) :
            if left>0 and nums[left] == nums[left-1]:
                continue
            # mid, right
            mid = left+1
            right = len(nums)-1
            while mid < right :
                sum = nums[left]+nums[mid]+nums[right]
                if sum < 0:
                    mid += 1
                elif sum>0 :
                    right -= 1           
                else : #sum==0
                    result.append([nums[left],nums[mid],nums[right]])
                    while mid<right and nums[mid]==nums[mid+1]:
                        mid +=1
                    while mid<right and nums[right]==nums[right-1]:
                        right-=1
                    mid+=1
                    right-=1
        return result

 

 

another approach

used set, tuple

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        # result should be 'set()' to avoid duplicates
        result =set()
        
        # 1. Split nums into three list
        negative, positive, zero = [], [], []
        for num in nums:
            if num==0:
                zero.append(num)
            elif num<0:
                negative.append(num)
            else:
                positive.append(num)
                
        # 2. Create a separate set for negatives and positives for O(1) look-up times
        N, P = set(negative), set(positive)
        
        # 3-1. IF there are at least 3 zeros in the list then also include (0,0,0)
        if len(zero) >=3 :
            result.add((0,0,0))
        
        # 3-2. If there is at least 1 zero in the list, add all cases where -num exist in N and num exists in P
        # i.e. (-3,0,3) = 0
        if zero :
            for value in P:
                if -1*value in N:
                    result.add((0, value, -value))
                    
        # 4-1. For all pairs of negative numbers (-3,-1), check to see if their complement (4)
        # exists in the positive number set
        for i in range(len(positive)-1):
            for j in range(i+1, len(positive)):
                sum = positive[i]+positive[j]
                if -sum in N:
                    result.add(tuple(sorted([positive[i], positive[j], -sum])))
        
        # 4-2. For all pairs of positive numbers (1, 1), check to see if their complement (-2) exists in the negative number set
        for i in range(len(negative)-1):
            for j in range(i+1, len(negative)):
                sum = negative[i]+negative[j]
                if -sum in P:
                    result.add(tuple(sorted([negative[i], negative[j], -sum])))
        
        return result