> [!META]- Inline Metadata > [tags:: #career #concepts/programming/algorithms/two-pointers ] > [project group:: Neetcode 150] > [difficulty:: medium] > [status:: done] > [link:: https://leetcode.com/problems/3sum/] > [up:: [[Leetcode MOC]]] ## Problem 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. **Example 1:** **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. **Example 2:** **Input:** nums = [0,1,1] **Output:** [] **Explanation:** The only possible triplet does not sum up to 0. **Example 3:** **Input:** nums = [0,0,0] **Output:** [[0,0,0]] **Explanation:** The only possible triplet sums up to 0. **Constraints:** - `3 <= nums.length <= 3000` - `-10^5 <= nums[i] <= 10^5` ## Solution ### Mine #### Python ```python class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: sorted_nums = sorted(nums) ans = [] for idx, num in enumerate(sorted_nums): if num > 0: break if idx > 0 and sorted_nums[idx - 1] == num: continue j = idx + 1 k = len(sorted_nums) - 1 while j <= len(sorted_nums) - 2 and j < k: summed = num + sorted_nums[j] + sorted_nums[k] if summed < 0: j += 1 elif summed > 0: k -= 1 else: ans.append([num, sorted_nums[j], sorted_nums[k]]) j += 1 while sorted_nums[j] == sorted_nums[j - 1] and j < k: j += 1 return ans ``` #### Rust ### Neetcode's ```python class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: res = [] nums.sort() for i, a in enumerate(nums): if i > 0 and a == nums[i - 1]: continue l, r = i + 1, len(nums) - 1 while l < r: threeSum = a + nums[l] + nums[r] if threeSum > 0: r -= 1 elif threeSum < 0: l += 1 else: res.append([a, nums[l], nums[r]]) l += 1 while nums[l] == nums[l - 1] and l < r: l += 1 return res ``` ## Things I Learned ### Neetcode Video Most brute force way would be a triple loop, but you can find duplicates this way (in addition to not being very time efficient). The solution would be to sort the input array. That means if you encounter a repeat for the first position, you can skip it, and you can do some optimizations like in [[167. Two Sum II - Input Array Is Sorted]]. Then what you can do is hold the first number steady, then use the [[167. Two Sum II - Input Array Is Sorted]] technique. You use two pointers, incrementing left if the sum < 0, decrementing right if sum > 0. Also change them if they equal the held-steady value. You can do this up until the "a" value is positive, then because it's sorted any sums won't equal 0 and you'll be done. Because we're sorting array, time complexity is $O(n\:log\:n) + O(n^2) \approx O(n^2)$ because of two loops for this implementation (one to iterate through each value for the first of the solution triplet, then the next nested one to do the two-sum solution). Space complexity could be $O(1)$ or $O(n)$ depending on implementation of sort. However, a difficulty is how you increment the pointers after finding a solution. This is because there are cases, like if the input was `[0, 0, 0, 0]` that just incrementing the left pointer and resetting the right pointer will get you duplicates. Instead you only have to update 1 pointer, then the if conditions in the first `while` loop will take care of updating the next pointer. You also have to ensure that the new left pointer doesn't point to an already seen number (just like in the `for` loop), so do a while loop to increment the left pointer while it points to a duplicate and is less than the value of the right pointer. ## Scratchpad ~~We can use a set for this, since there is no constraint on extra space. Use two pointers to get first two candidates, then check in set for needed 3rd to reach 0. If it's in there, it's added to the list.~~ Actually, the set wouldn't be useful because if we have a case where the third number we want is the same as one of the existing 2, it will show up in the set even though it's not present. Brute force way would be to sort input list first. This makes the operation *at least* $O(n\:log\:n)$ time. But let's start with that. Forget it. Another option that may work, is to make an intermediate list of sets using only indices of the input. Nope. I have a really stupid idea. Use two pointers to get a list of all intermediate sums. As we cycle through, we also add each value to a dictionary as a key, and the value is a set of all the indices that have that value. For each intermediate sum, see if its complement is in the dictionary ($O(1)$ lookup) and get the indices associated with it. If none of them are an index associated witht he intermediate sum, add it to the list. This means the intermediate sum should also be in a dictionary with the values being a set of the indices that make it up. This actually won't work if there is more than one set of indices that have the same sum. Giving up and watching the video.