Three Sum Problem All Unique Triplets in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to sort the input list before processing.

DSA Python

nums = [3, 0, -2, -1, 1, 2]
nums.[1]()

Drag options to blanks, or click blank then click option'

Areverse

Bsorted

Csort

Dappend

Attempts:

3 left

💡 Hint

Common Mistakes

Using sorted() which returns a new list but does not change the original list.

Using reverse() which only reverses the list order.

We use the sort() method to sort the list in place before finding triplets.

2fill in blank

medium

Complete the code to skip duplicate elements for the first pointer in the triplet search.

DSA Python

for i in range(len(nums)):
    if i > 0 and nums[i] == nums[1]:
        continue

Drag options to blanks, or click blank then click option'

A-1

Bi+1

C0

Di-1

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with the next element instead of the previous.

Using an invalid index like 0 or -1 incorrectly.

We compare the current element with the previous one to skip duplicates.

3fill in blank

hard

Fix the error in the while loop condition to correctly move the left pointer.

DSA Python

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

Drag options to blanks, or click blank then click option'

Aleft-1

Bleft+1

Cright-1

Dright+1

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with the next element which may cause index errors.

Using right pointer indices incorrectly.

We compare the current left element with the previous left element to skip duplicates.

4fill in blank

hard

Fill both blanks to correctly move the right pointer and skip duplicates after finding a valid triplet.

DSA Python

while left < right and nums[right] == nums[1]:
    right = [2]

Drag options to blanks, or click blank then click option'

Aright+1

Bright-1

Cleft+1

Dleft-1

Attempts:

3 left

💡 Hint

Common Mistakes

Increasing the right pointer which goes out of bounds.

Comparing with left pointer indices.

We compare the current right element with the previous right element and move the right pointer leftwards to skip duplicates.

5fill in blank

hard

Fill all three blanks to complete the dictionary comprehension that counts the frequency of each number in the list.

DSA Python

count = [1](num: nums.count(num) for num in [2])
unique_nums = sorted(count.[3]())

Drag options to blanks, or click blank then click option'

Adict

Bnums

Ckeys

Dlist

Attempts:

3 left

💡 Hint

Common Mistakes

Using list instead of dict for the comprehension.

Iterating over dictionary keys instead of the original list.

Using values() instead of keys().

We use dict to create a dictionary, iterate over nums, and get the keys from the dictionary to sort unique numbers.

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