Framework Thinking - Neetcode 150 - 3Sum
1. Understand the problem
-
Input: array nums (integers).
-
Output: list of unique triplets [x,y,z] (each a list of three ints) where x + y + z == 0.
-
Each triplet should be sorted (conceptually) or at least duplicates must be avoided (e.g., [-1,0,1] and [0,-1,1] are the same and only one should appear).
-
Order of triplets in the output does not matter.
2. Clarifying questions
-
Are there any bounds on n and element magnitude? (Commonly n ≤ 2000, elements fit in 32-bit.)
-
Should triplets be unique regardless of order? (Yes — unique sets.)
-
Are duplicates in input allowed? (Yes.)
-
What complexity do you expect? (Aim for O(n^2) time, O(1) or O(n) extra space.)
-
Edge cases to consider: empty array, length < 3, all zeros, all positive or all negative.
3. Work through examples
-
[-1, 0, 1, 2, -1, -4] → expected [[ -1, -1, 2], [ -1, 0, 1]]
-
[0,0,0] → [[0,0,0]]
-
[] → []
-
[0,0,0,0] → [[0,0,0]] (duplicates in input produce one triplet)
-
[-2,0,1,1,2] → [[-2,0,2], [-2,1,1]]
-
[1,2,-2,-1] → [] (no triple sums to 0)
4. Brainstorm 2–3 solutions
4.1. Brute force (naive)
-
Try all triplets i<j<k: O(n^3) time.
-
Use a set to filter duplicates or sort each triplet before adding to set.
-
Space: O(triplets) for result.
4.2. Hash-based improvement (target = -nums[i])
-
For each i, solve 2Sum for target -nums[i] using a hash set (or map) to find pairs in O(n).
-
Time: O(N^2).
-
Space: O(N).
4.3. Sort + Two-pointer (recommended)
-
Sort nums first. For each index i (0..n-3) with value a = nums[i], set target = -a. Use two pointers l = i+1 and r = n-1 to find pairs summing to target.
-
Time: O(N^2).
-
Space: O(1).
5. Implement solutions
5.1. Brute force
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = set()
nums.sort()
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
for k in range(j + 1, len(nums)):
if nums[i] + nums[j] + nums[k] == 0:
tmp = [nums[i], nums[j], nums[k]]
res.add(tuple(tmp))
return [list(i) for i in res]
-
Time complexity: O(N^3).
-
Space complexity: O(N)
5.2. Hash Map
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
count = defaultdict(int)
for num in nums:
count[num] += 1
res = []
for i in range(len(nums)):
# Fixed number 1
count[nums[i]] -= 1
if i and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, len(nums)):
# Fixed number 2
count[nums[j]] -= 1
if j - 1 > i and nums[j] == nums[j - 1]:
continue
# Use hashmap for O(1)
target = -(nums[i] + nums[j])
if count[target] > 0:
res.append([nums[i], nums[j], target])
for j in range(i + 1, len(nums)):
count[nums[j]] += 1
return res
-
Time complexity: O(N^2).
-
Space complexity: O(N)
5.3. Two Pointers
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for i, a in enumerate(nums):
if a > 0:
break
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
r -= 1
while nums[l] == nums[l - 1] and l < r:
l += 1
while nums[r] == nums[r + 1] and l < r:
r -= 1
return res
-
Time complexity: O(N^2).
-
Space complexity: O(1).
6. Run the test case
nums = [-4, -1, -1, 0, 1, 2]
count = {-4:1, -1:2, 0:1, 1:1, 2:1}
- Skip the first number => O(N) two pairs.