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.

Practice

1. What is the main goal of the Three Sum Problem in arrays?

easy

A. Find all unique triplets that sum to zero

B. Find the maximum sum of any three elements

C. Sort the array in ascending order

D. Count the number of pairs with sum zero

Solution

1. Step 1: Understand the problem statement

   The Three Sum Problem asks to find all unique sets of three numbers in an array that add up to zero.

2. Step 2: Differentiate from other sum problems

   Unlike finding pairs or maximum sums, this problem focuses on triplets with sum exactly zero and uniqueness.

3. Final Answer:

   Find all unique triplets that sum to zero -> Option A

4. Quick Check:

   Three Sum = unique triplets summing to zero [OK]

Hint: Look for three numbers adding exactly to zero [OK]

Common Mistakes:

• Confusing with pair sum problems
• Looking for maximum sum instead of zero sum
• Ignoring uniqueness of triplets

2. Which of the following Python code snippets correctly initializes an empty list to store unique triplets for the Three Sum Problem?

easy

A. triplets = []

B. triplets = {}

C. triplets = set()

D. triplets = None

Solution

1. Step 1: Identify the correct data structure for storing triplets

   Triplets are stored as lists inside a list, so initializing an empty list is correct.

2. Step 2: Analyze other options

   {} creates a dictionary, set() is for unique single elements, None is not a container.

3. Final Answer:

   triplets = [] -> Option A

4. Quick Check:

   Empty list for triplets = [] [OK]

Hint: Use [] to store multiple triplets as lists [OK]

Common Mistakes:

• Using {} which creates a dictionary
• Using set() which stores unique single elements, not lists
• Assigning None which is not a container

3. What is the output of the following code snippet for the input array nums = [-1, 0, 1, 2, -1, -4]?

def three_sum(nums):
    nums.sort()
    result = []
    for i in range(len(nums)-2):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        left, right = i+1, len(nums)-1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                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 total < 0:
                left += 1
            else:
                right -= 1
    return result

print(three_sum(nums))

medium

A. []

B. [[-1, 0, 1], [0, 1, 2]]

C. [[0, 0, 0]]

D. [[-1, -1, 2], [-1, 0, 1]]

Solution

1. Step 1: Sort the input array

   Sorted nums = [-4, -1, -1, 0, 1, 2]

2. Step 2: Find unique triplets summing to zero

   Triplets found are [-1, -1, 2] and [-1, 0, 1]. These are appended to result.

3. Final Answer:

   [[-1, -1, 2], [-1, 0, 1]] -> Option D

4. Quick Check:

   Triplets sum zero = [[-1,-1,2],[-1,0,1]] [OK]

Hint: Sort array and use two pointers to find triplets [OK]

Common Mistakes:

• Not sorting the array before processing
• Including duplicate triplets
• Incorrect pointer movement causing missed triplets

4. Identify the bug in the following code snippet for the Three Sum Problem:

def three_sum(nums):
    nums.sort()
    result = []
    for i in range(len(nums)):
        left, right = i+1, len(nums)-1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return result

print(three_sum([-1, 0, 1, 2, -1, -4]))

medium

A. The outer loop should run till len(nums)-2, not len(nums)

B. No check to skip duplicate triplets

C. Missing sorting of the input array

D. Incorrect initialization of left and right pointers

Solution

1. Step 1: Check for duplicate skipping logic

   The code lacks 'if i > 0 and nums[i] == nums[i-1]: continue' and inner while loops to skip duplicate left/right values after finding a triplet. This causes duplicate triplets like [-1, 0, 1] appearing twice.

2. Step 2: Verify other parts

   Sorting is present, pointers initialized correctly, loop range to len(nums) is unnecessary but does not cause errors or duplicates.

3. Final Answer:

   No check to skip duplicate triplets -> Option B

4. Quick Check:

   Missing duplicate skips cause repeated triplets [OK]

Hint: Add duplicate skips for i, left, and right pointers [OK]

Common Mistakes:

• Missing 'if i > 0 and nums[i] == nums[i-1]' check
• No inner while loops to skip duplicate left/right
• Thinking loop range causes index errors (it doesn't)

5. Given the input array nums = [0, 0, 0, 0], what is the correct output of a Three Sum solution that returns all unique triplets summing to zero?

hard

A. [[0, 0, 0], [0, 0, 0]]

B. []

C. [[0, 0, 0]]

D. [[0, 0]]

Solution

1. Step 1: Understand uniqueness requirement

   Even though multiple zeros exist, only one unique triplet [0, 0, 0] should be returned.

2. Step 2: Check triplet formation

   Triplet [0, 0, 0] sums to zero and is valid. Duplicates must be avoided.

3. Final Answer:

   [[0, 0, 0]] -> Option C

4. Quick Check:

   Unique triplets = [[0,0,0]] [OK]

Hint: Return only unique triplets, avoid duplicates [OK]

Common Mistakes:

• Returning duplicate triplets multiple times
• Returning pairs instead of triplets
• Returning empty list when triplets exist