15.3Sum(Medium).md

15. 3Sum (Medium)

Date and Time: Jul 9, 2024, 16:25 (EST)

Link: https://leetcode.com/problems/3sum/

Edge case:

Input: nums = [-1, 0, 1, -1, 0, 1]

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

Walk-through:

We can reduce the 3Sum problem into Two Sum II Problem by sorting nums first, then start with the first entry in triplets by looping over nums, and set two pointers l, r by l = i + 1, r = len(nums)-1. Each time we calculate the curr by taking the sum of these three elements, and if curr < 0 we increment l because nums is sorted and we move l to the right to increment curr, the same case when curr > 0.

For the first if statement, we want to check there is no duplicate when we start with the first element. Look at Example 1, after nums.sort(), nums = [-4, -1, -1, 0, 1, 2], so when nums[1] = nums[2] = -1, we don't want to check nums[2], so we continue. Similar reasoning for Edge case, when nums = [-1, -1, 0, 0, 1, 1], if we don't skip when nums[l] = nums[l+1] = 0, we will have duplicate result that [[-1, 0, 1], [-1, 0, 1]].

My Solution:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        for i in range(len(nums)):
            # When the first element have duplicate from previous one, just skip
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l, r = i + 1, len(nums)-1
            while l < r:
                curr = nums[i] + nums[l] + nums[r]
                if curr < 0:
                    l += 1
                elif curr > 0:
                    r -= 1
                else:
                    res.append([nums[i], nums[l], nums[r]])
                    l += 1
                    # Check if the second element has the next same element, skip
                    while l < r and nums[l] == nums[l-1]:
                        l += 1
        return res

Time Complexity: $O(n^2)$
Space Complexity: $O(n)$