Three Sum Problem All Unique Triplets in DSA Python - Build from Scratch

Three Sum Problem All Unique Triplets

📖 Scenario: You are working on a financial app that analyzes a list of daily profit and loss numbers. You want to find all unique sets of three days where the total profit/loss sums to zero. This helps identify balanced periods.

🎯 Goal: Build a program that finds all unique triplets in a list of integers that add up to zero.

📋 What You'll Learn

Create a list called nums with the exact integers: -1, 0, 1, 2, -1, -4

Create a variable called result to store the unique triplets

Use a sorted version of nums to help find triplets

Implement the two-pointer technique inside a loop to find all triplets that sum to zero

Print the result list containing all unique triplets

💡 Why This Matters

🌍 Real World

Finding balanced sets of financial transactions or data points that sum to zero can help detect patterns or anomalies.

💼 Career

This problem is common in coding interviews and helps develop skills in sorting, two-pointer technique, and handling duplicates.

1

Create the list of numbers

Create a list called nums with these exact integers: -1, 0, 1, 2, -1, -4

DSA Python

# Create the list nums with the given integers
# Your code here

Hint

Use square brackets to create the list and separate numbers with commas.

2

Initialize the result list and sort the numbers

Create a variable called result as an empty list to store triplets. Then create a variable called nums_sorted that holds the sorted version of nums.

DSA Python

nums = [-1, 0, 1, 2, -1, -4]
# Initialize result as an empty list
# Create nums_sorted as sorted(nums)
# Your code here

Hint

Use [] for an empty list and the sorted() function to sort.

3

Find all unique triplets that sum to zero

Use a for loop with variable i to iterate over nums_sorted up to length minus 2. Inside the loop, skip duplicates by checking if i > 0 and nums_sorted[i] == nums_sorted[i-1]. Then set two pointers: left = i + 1 and right = len(nums_sorted) - 1. Use a while loop to move left and right pointers to find triplets where the sum of nums_sorted[i] + nums_sorted[left] + nums_sorted[right] is zero. Add unique triplets to result. Skip duplicates for left and right pointers as well.

DSA Python

nums = [-1, 0, 1, 2, -1, -4]
result = []
nums_sorted = sorted(nums)
# Use a for loop with i to find triplets
# Your code here

Hint

Use two pointers moving inward to find sums equal to zero. Skip duplicates to avoid repeated triplets.

4

Print the list of unique triplets

Print the variable result to display all unique triplets that sum to zero.

DSA Python

nums = [-1, 0, 1, 2, -1, -4]
result = []
nums_sorted = sorted(nums)

for i in range(len(nums_sorted) - 2):
    if i > 0 and nums_sorted[i] == nums_sorted[i - 1]:
        continue
    left = i + 1
    right = len(nums_sorted) - 1
    while left < right:
        total = nums_sorted[i] + nums_sorted[left] + nums_sorted[right]
        if total == 0:
            result.append([nums_sorted[i], nums_sorted[left], nums_sorted[right]])
            while left < right and nums_sorted[left] == nums_sorted[left + 1]:
                left += 1
            while left < right and nums_sorted[right] == nums_sorted[right - 1]:
                right -= 1
            left += 1
            right -= 1
        elif total < 0:
            left += 1
        else:
            right -= 1
# Print the result list
# Your code here

Hint

Use print(result) to show the final list of 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