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.