Three Sum Problem All Unique Triplets in DSA Python

Mental Model

Find three numbers in a list that add up to zero without repeating the same triplet.

Analogy: Imagine you have a group of friends with different amounts of money. You want to find three friends whose combined money adds up to zero, like balancing debts and credits exactly.

nums: [-4] -> [-1] -> [-1] -> [0] -> [1] -> [2] -> null
indexes:  0       1       2       3      4      5

Dry Run Walkthrough

Input: list: [-1, 0, 1, 2, -1, -4]

Goal: Find all unique triplets that sum to zero

Step 1: Sort the list to make it easier to find triplets

[-4] -> [-1] -> [-1] -> [0] -> [1] -> [2]

Why: Sorting helps us use two pointers to find pairs efficiently

Step 2: Fix first number at index 0 (-4), set left=1, right=5

fixed=-4, left=-1, right=2

Why: We try to find two numbers that sum to 4 (because -4 + x + y = 0 means x + y = 4)

Step 3: Sum = -4 + (-1) + 2 = -3, less than 0, move left pointer right

fixed=-4, left=-1 (index 2), right=2

Why: Sum too small, increase left to get bigger sum

Step 4: Sum = -4 + (-1) + 2 = -3, still less than 0, move left pointer right

fixed=-4, left=0 (index 3), right=2

Why: Keep increasing left to find sum closer to zero

Step 5: Sum = -4 + 0 + 2 = -2, less than 0, move left pointer right

fixed=-4, left=1 (index 4), right=2

Why: Sum still too small, move left pointer

Step 6: Sum = -4 + 1 + 2 = -1, less than 0, move left pointer right

fixed=-4, left=2 (index 5), right=2

Why: Left pointer meets right, no triplet with fixed=-4

Step 7: Fix first number at index 1 (-1), set left=2, right=5

fixed=-1, left=-1, right=2

Why: Try to find two numbers that sum to 1

Step 8: Sum = -1 + (-1) + 2 = 0, found triplet [-1, -1, 2], move left and right to avoid duplicates

triplets=[[-1, -1, 2]], left=3, right=4

Why: Found valid triplet, move pointers to find others

Step 9: Sum = -1 + 0 + 1 = 0, found triplet [-1, 0, 1], move left and right

triplets=[[-1, -1, 2], [-1, 0, 1]], left=4, right=3

Why: Found another triplet, pointers crossed, move to next fixed

Step 10: Fix first number at index 2 (-1), skip because same as previous fixed

skip fixed=-1 at index 2

Why: Avoid duplicate triplets by skipping same fixed number

Step 11: Fix first number at index 3 (0), set left=4, right=5

fixed=0, left=4, right=5

Why: Try to find two numbers that sum to 0

Step 12: Sum = 0 + 1 + 2 = 3, greater than 0, move right pointer left

fixed=0, left=4, right=4

Why: Sum too big, decrease right pointer

Step 13: Left pointer meets right, no triplet with fixed=0

end fixed=0

Why: No more pairs to check

Result:

[-1] -> [-1] -> [2] and [-1] -> [0] -> [1]

Annotated Code

DSA Python

from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()  # sort the list to use two pointers
        triplets = []
        n = len(nums)
        for i in range(n):
            if i > 0 and nums[i] == nums[i - 1]:
                continue  # skip duplicate fixed numbers
            left, right = i + 1, n - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total == 0:
                    triplets.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1  # skip duplicates
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1  # skip duplicates
                elif total < 0:
                    left += 1  # need bigger sum
                else:
                    right -= 1  # need smaller sum
        return triplets

# Driver code
sol = Solution()
input_list = [-1, 0, 1, 2, -1, -4]
result = sol.threeSum(input_list)
for triplet in result:
    print(triplet)

nums.sort() # sort the list to use two pointers

sort input to enable two-pointer technique

if i > 0 and nums[i] == nums[i - 1]: continue # skip duplicate fixed numbers

skip duplicate fixed elements to avoid repeated triplets

left, right = i + 1, n - 1

initialize two pointers after fixed element

total = nums[i] + nums[left] + nums[right]

calculate sum of current triplet

if total == 0: triplets.append([nums[i], nums[left], nums[right]])

found valid triplet, add to result

left += 1 right -= 1

move pointers inward to find new pairs

while left < right and nums[left] == nums[left - 1]: left += 1 # skip duplicates

skip duplicate left elements

while left < right and nums[right] == nums[right + 1]: right -= 1 # skip duplicates

skip duplicate right elements

elif total < 0: left += 1 # need bigger sum

sum too small, move left pointer right

else: right -= 1 # need smaller sum

sum too big, move right pointer left

Output

[-1, -1, 2]

[-1, 0, 1]

Complexity Analysis

Time: O(n^2) because we sort once O(n log n) and then use two nested loops with two pointers

Space: O(k) where k is number of triplets found, for storing results

vs Alternative: Naive approach is O(n^3) by checking all triplets; two-pointer reduces to O(n^2)

Edge Cases

empty list

returns empty list, no triplets

DSA Python

for i in range(n): (loop does not run if n=0)

list with less than 3 elements

returns empty list, no triplets possible

DSA Python

for i in range(n): (loop runs but inner while left<right fails)

list with all zeros

returns one triplet [0,0,0] without duplicates

DSA Python

while left < right and nums[left] == nums[left - 1]: left += 1

When to Use This Pattern

When asked to find triplets summing to zero or a target with unique results, use sorting plus two-pointer approach to efficiently find pairs.

Common Mistakes

Mistake: Not sorting the list before applying two pointers
Fix: Sort the list first to enable two-pointer technique

Mistake: Not skipping duplicates for fixed, left, or right pointers
Fix: Add checks to skip duplicates to avoid repeated triplets

Mistake: Moving pointers incorrectly when sum equals zero
Fix: Move both pointers inward and skip duplicates after finding a valid triplet

Summary

Finds all unique triplets in a list that sum to zero.

Use when you need to find combinations of three numbers adding to zero without repeats.

Sort the list and use a fixed pointer plus two pointers to efficiently find triplets.