Why Three Sum Problem All Unique Triplets in DSA Python?

The Big Idea

What if you could find all zero-sum triplets in seconds instead of hours?

The Scenario

Imagine you have a list of numbers and you want to find all groups of three numbers that add up to zero. Doing this by hand means checking every possible group of three numbers one by one.

The Problem

Checking every group manually is very slow and tiring because the number of groups grows very fast as the list gets bigger. It's easy to miss some groups or count the same group more than once.

The Solution

The Three Sum problem uses a smart way to find all unique groups of three numbers that add up to zero without checking every group. It sorts the list and uses two pointers to quickly find matching pairs, making the process much faster and less error-prone.

Before vs After

✗ Before

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:
                print(nums[i], nums[j], nums[k])

✓ After

nums.sort()
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:
            left += 1
        elif total > 0:
            right -= 1
        else:
            print(nums[i], nums[left], nums[right])
            left += 1
            while left < right and nums[left] == nums[left-1]:
                left += 1
            right -= 1
            while left < right and nums[right] == nums[right+1]:
                right -= 1

What It Enables

This method lets you quickly find all unique triplets that sum to zero, even in large lists, without missing any or repeating groups.

Real Life Example

Finding three expenses that together balance out to zero in a financial report, helping to spot errors or fraud quickly.

Key Takeaways

Manual checking is slow and error-prone for finding triplets.

Sorting and two-pointer technique speeds up the search.

Ensures all unique triplets are found without repeats.

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