Three Sum Problem All Unique Triplets in DSA Python - Execution Trace

Concept Flow - Three Sum Problem All Unique Triplets

Sort the array

↓

Fix first element i

↓

Set left = i+1, right = end

↓

Calculate sum = nums[i

↓

Add triplet

↓

Move left and right skipping duplicates

↓

Move left right to increase sum

↓

Move right left to decrease sum

↓

Repeat until left >= right

↓

Move i to next unique element

↓

Repeat until i reaches end

↓

Return all unique triplets

We sort the array, then fix one element and use two pointers to find pairs that sum to zero with it, skipping duplicates to get unique triplets.

Execution Sample

DSA Python

nums = [-1, 0, 1, 2, -1, -4]
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:
    s = nums[i] + nums[left] + nums[right]
    if s == 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 s < 0:
      left += 1
    else:
      right -= 1

This code sorts the array and uses a fixed pointer with two moving pointers to find triplets summing to zero.

Execution Table

Step	Operation	i	left	right	Sum	Triplets Found	Pointer Changes	Array State
1	Sort array	-	-	-	-	[]	-	[-4, -1, -1, 0, 1, 2]
2	Fix i at 0	0	1	5	-	[]	Set left=1, right=5	[-4, -1, -1, 0, 1, 2]
3	Calculate sum	0	1	5	-4 + (-1) + 2 = -3	[]	sum < 0, move left right	[-4, -1, -1, 0, 1, 2]
4	Move left	0	2	5	-	[]	left=2	[-4, -1, -1, 0, 1, 2]
5	Calculate sum	0	2	5	-4 + (-1) + 2 = -3	[]	sum < 0, move left right	[-4, -1, -1, 0, 1, 2]
6	Move left	0	3	5	-	[]	left=3	[-4, -1, -1, 0, 1, 2]
7	Calculate sum	0	3	5	-4 + 0 + 2 = -2	[]	sum < 0, move left right	[-4, -1, -1, 0, 1, 2]
8	Move left	0	4	5	-	[]	left=4	[-4, -1, -1, 0, 1, 2]
9	Calculate sum	0	4	5	-4 + 1 + 2 = -1	[]	sum < 0, move left right	[-4, -1, -1, 0, 1, 2]
10	Move left	0	5	5	-	[]	left=5	[-4, -1, -1, 0, 1, 2]
11	left >= right	0	5	5	-	[]	End inner loop	[-4, -1, -1, 0, 1, 2]
12	Move i to 1	1	2	5	-	[]	Skip duplicates for i	[-4, -1, -1, 0, 1, 2]
13	Calculate sum	1	2	5	-1 + (-1) + 2 = 0	[[-1, -1, 2]]	sum == 0, add triplet, move left and right skipping duplicates	[-4, -1, -1, 0, 1, 2]
14	Move left	1	3	4	-	[[-1, -1, 2]]	left=3	[-4, -1, -1, 0, 1, 2]
15	Move right	1	3	4	-	[[-1, -1, 2]]	right=4	[-4, -1, -1, 0, 1, 2]
16	Calculate sum	1	3	4	-1 + 0 + 1 = 0	[[-1, -1, 2], [-1, 0, 1]]	sum == 0, add triplet, move left and right skipping duplicates	[-4, -1, -1, 0, 1, 2]
17	Move left	1	4	3	-	[[-1, -1, 2], [-1, 0, 1]]	left=4	[-4, -1, -1, 0, 1, 2]
18	left >= right	1	4	3	-	[[-1, -1, 2], [-1, 0, 1]]	End inner loop	[-4, -1, -1, 0, 1, 2]
19	Move i to 2	2	-	-	-	[[-1, -1, 2], [-1, 0, 1]]	Skip duplicate i=2 because nums[2] == nums[1]	[-4, -1, -1, 0, 1, 2]
20	Move i to 3	3	4	5	-	[[-1, -1, 2], [-1, 0, 1]]	Set left=4, right=5	[-4, -1, -1, 0, 1, 2]
21	Calculate sum	3	4	5	0 + 1 + 2 = 3	[[-1, -1, 2], [-1, 0, 1]]	sum > 0, move right left	[-4, -1, -1, 0, 1, 2]
22	Move right	3	4	4	-	[[-1, -1, 2], [-1, 0, 1]]	right=4	[-4, -1, -1, 0, 1, 2]
23	left >= right	3	4	4	-	[[-1, -1, 2], [-1, 0, 1]]	End inner loop	[-4, -1, -1, 0, 1, 2]
24	Move i to 4	4	-	-	-	[[-1, -1, 2], [-1, 0, 1]]	i reaches len(nums)-2, end loop	[-4, -1, -1, 0, 1, 2]

💡 i reaches len(nums)-2, no more triplets possible

Variable Tracker

Variable	Start	After Step 2	After Step 12	After Step 20	Final
i	-	0	1	3	4
left	-	1	2	4	4
right	-	5	5	5	4
Triplets Found	[]	[]	[[-1, -1, 2]]	[[-1, -1, 2], [-1, 0, 1]]	[[-1, -1, 2], [-1, 0, 1]]
Array State	[-1, 0, 1, 2, -1, -4]	[-4, -1, -1, 0, 1, 2]	[-4, -1, -1, 0, 1, 2]	[-4, -1, -1, 0, 1, 2]	[-4, -1, -1, 0, 1, 2]

Key Moments - 3 Insights

Why do we skip duplicate values for i and left/right pointers?

Skipping duplicates prevents adding the same triplet multiple times. For example, at step 19, i=2 is skipped because nums[2] == nums[1], avoiding repeated triplets as shown in execution_table rows 13-18.

Why do we move left pointer when sum < 0 and right pointer when sum > 0?

Because the array is sorted, moving left pointer right increases sum, and moving right pointer left decreases sum. This is shown in steps 3-10 and 21-22 in the execution_table.

Why does the inner loop stop when left >= right?

When left meets or passes right, all pairs for the fixed i are checked. This is shown at steps 11, 18, 23 where the inner loop ends.

Visual Quiz - 3 Questions

Look at the execution_table at step 13, what triplet is added to the result?

A [-1, -1, 2]

B [-1, 0, 1]

C [-4, 1, 2]

D [0, 1, 2]

💡 Hint

Check the 'Triplets Found' column at step 13 in execution_table

At which step does the sum first equal zero?

A Step 3

B Step 13

C Step 16

D Step 21

💡 Hint

Look at the 'Sum' column in execution_table and find the first zero value

If we did not skip duplicates for i, what would happen in the execution?

A More unique triplets would be found

B The algorithm would run faster

C Duplicate triplets would be added multiple times

D No triplets would be found

💡 Hint

Refer to key_moments about skipping duplicates and step 19 in execution_table

Concept Snapshot

Three Sum Problem:
- Sort the array first
- Fix one element i
- Use two pointers left=i+1 and right=end
- Calculate sum = nums[i]+nums[left]+nums[right]
- If sum==0, add triplet and skip duplicates
- If sum<0, move left right to increase sum
- If sum>0, move right left to decrease sum
- Repeat until all unique triplets found

Full Transcript

The Three Sum problem finds all unique triplets in an array that sum to zero. We start by sorting the array to use the two-pointer technique efficiently. We fix one element at a time and set two pointers: one just after the fixed element and one at the end of the array. We calculate the sum of these three elements. If the sum is zero, we add the triplet to the result and move both pointers skipping duplicates to avoid repeated triplets. If the sum is less than zero, we move the left pointer right to increase the sum. If the sum is greater than zero, we move the right pointer left to decrease the sum. We repeat this process until the pointers meet. Then we move the fixed element to the next unique value and repeat. This approach ensures all unique triplets are found efficiently.

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