[Leetcode] 3Sum

https://neetcode.io/problems/three-integer-sum?list=neetcode150

initial

so i didnt know how at all. First we cannot have duplicate combis so once we find a valid case we should skip the duplicates.

We realise that nums[i]+nums[j]+nums[k]=0. So if we fix nums[i], we get a 2 sum problem. We need a sorted list to get the sum of nums[j] and nums[k] as a pattern. And once we find valid case we shift left and right pointer to not have duplicate values as that previous values.

sol

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        ans = []
        nums.sort()
        
        # Your loop: for(int i=0; i<n-2; i++)
        for i in range(n - 2):
            # Your check: if(i>0 && nums[i-1]==nums[i]) continue;
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            
            left, right = i + 1, n - 1
            
            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]
                
                if current_sum == 0:
                    # Your addition: ans.add(Arrays.asList(...))
                    ans.append([nums[i], nums[left], nums[right]])
                    
                    # Your duplicate skips:
                    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 current_sum < 0:
                    left += 1
                else:
                    right -= 1
                    
        return ans

complexity

is it n log n time and n space

no
sorting is n log n but the outer loop is n but the inner loop(2 sum) is also o(n) in worst case so n^2. so it is n^2.

its 1 space