Four Sum Problem All Unique Quadruplets in DSA Python - Execution Trace

Concept Flow - Four Sum Problem All Unique Quadruplets

Sort the array

↓

Fix first number i

↓

Fix second number j

↓

Set left = j+1, right = end

↓

While left < right

Skip duplicates Repeat Repeat↓

Move j to next unique

↓

Move i to next unique

↓

Done

↩Skip duplicates Repeat Repeat

We sort the array, then pick two numbers with two pointers to find quadruplets summing to target, skipping duplicates.

Execution Sample

DSA Python

nums = [1, 0, -1, 0, -2, 2]
target = 0
# Find all unique quadruplets
# that sum to target

This code finds all unique sets of four numbers in nums that add up to zero.

Execution Table

Step	Operation	i,j,left,right	Sum	Quadruplet Found	Skip Duplicates	Visual State (Quadruplets)
1	Sort array	-	-	-	-	[-2, -1, 0, 0, 1, 2]
2	Fix i=0	i=0	-	-	-	Start with i at -2
3	Fix j=1	i=0, j=1	-	-	-	j at -1
4	Set left=2, right=5	i=0, j=1, left=2, right=5	-	-	-	left=2, right=5
5	Calculate sum	i=0, j=1, left=2, right=5	-2 + -1 + 0 + 2 = -1	No	No	[]
6	Sum < target, move left	i=0, j=1, left=3, right=5	-	-	-	left moves to 3
7	Calculate sum	i=0, j=1, left=3, right=5	-2 + -1 + 0 + 2 = -1	No	No	[]
8	Sum < target, move left	i=0, j=1, left=4, right=5	-	-	-	left moves to 4
9	Calculate sum	i=0, j=1, left=4, right=5	-2 + -1 + 1 + 2 = 0	Yes	No	[[-2, -1, 1, 2]]
10	Skip duplicates left/right	i=0, j=1, left=5, right=4	-	-	left > right, exit while	[[-2, -1, 1, 2]]
11	Move j to next unique	i=0, j=2	-	-	-	j at 0
12	Set left=3, right=5	i=0, j=2, left=3, right=5	-	-	-	left=3, right=5
13	Calculate sum	i=0, j=2, left=3, right=5	-2 + 0 + 0 + 2 = 0	Yes	Skip left duplicate	[[-2, -1, 1, 2], [-2, 0, 0, 2]]
14	Skip duplicates left/right	i=0, j=2, left=4, right=4	-	-	left >= right, exit while	[[-2, -1, 1, 2], [-2, 0, 0, 2]]
15	Move j to next unique	i=0, j=3	-	-	Skip j=3 because nums[3] == nums[2]	Skip duplicate j
16	Move i to next unique	i=1	-	-	-	i at -1
17	Fix j=2	i=1, j=2	-	-	-	j at 0
18	Set left=3, right=5	i=1, j=2, left=3, right=5	-	-	-	left=3, right=5
19	Calculate sum	i=1, j=2, left=3, right=5	-1 + 0 + 0 + 2 = 1	No	No	[[-2, -1, 1, 2], [-2, 0, 0, 2]]
20	Sum > target, move right	i=1, j=2, left=3, right=4	-	-	-	right moves to 4
21	Calculate sum	i=1, j=2, left=3, right=4	-1 + 0 + 0 + 1 = 0	Yes	No	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
22	Skip duplicates left/right	i=1, j=2, left=4, right=3	-	-	left > right, exit while	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
23	Move j to next unique	i=1, j=3	-	-	Skip j=3 duplicate	Skip duplicate j
24	Move i to next unique	i=2	-	-	-	i at 0
25	Fix j=3	i=2, j=3	-	-	-	j at 0 (index 3)
26	Set left=4, right=5	i=2, j=3, left=4, right=5	-	-	-	left=4, right=5
27	Calculate sum	i=2, j=3, left=4, right=5	0 + 0 + 1 + 2 = 3	No	No	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
28	Sum > target, move right	i=2, j=3, left=4, right=4	-	-	-	right moves to 4
29	left >= right, exit while	i=2, j=3, left=4, right=4	-	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
30	Move j to next unique	i=2, j=4	-	-	j out of range, exit j loop	Done with j
31	Move i to next unique	i=3	-	-	i out of range, exit i loop	Done with i
32	Return result	-	-	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

💡 i and j loops finished, all quadruplets found

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 9	After Step 13	After Step 21	Final
i	-	0	0	0	0	1	2
j	-	-	1	1	2	2	3
left	-	-	2	4	4	4	-
right	-	-	5	5	5	4	-
Quadruplets	[]	[]	[[-2, -1, 1, 2]]	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

Key Moments - 3 Insights

Why do we skip duplicates for i, j, left, and right pointers?

Skipping duplicates prevents adding the same quadruplet multiple times. For example, after finding a quadruplet at step 9, we skip duplicate values at left and right to avoid repeats, as shown in steps 10 and 14.

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

Because the array is sorted, moving left pointer right increases sum, and moving right pointer left decreases sum. This helps find the target sum efficiently, as seen in steps 6, 8, 20, and 27.

Why do we stop the while loop when left >= right?

When left meets or passes right, all pairs between j and end are checked for current i and j. No more pairs remain, so we move to next j or i, as in steps 10, 14, 22, 29.

Visual Quiz - 3 Questions

Look at the execution table at step 9. What quadruplet is found?

A [-2, -1, 1, 2]

B [-2, 0, 0, 2]

C [-1, 0, 0, 1]

D [0, 0, 1, 2]

💡 Hint

Check the 'Quadruplet Found' and 'Visual State' columns at step 9.

At which step does the left pointer move because sum < target for the first time?

A Step 5

B Step 9

C Step 6

D Step 20

💡 Hint

Look at the 'Sum' and 'Action' columns around steps 5 and 6.

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

A No quadruplets would be found

B More quadruplets would be found, including duplicates

C The algorithm would run faster

D The sum calculation would be incorrect

💡 Hint

Refer to steps 15 and 23 where duplicates for j are skipped.

Concept Snapshot

Four Sum Problem:
- Sort array first
- Use two loops for i and j
- Use two pointers left and right
- Move pointers based on sum vs target
- Skip duplicates for i, j, left, right
- Collect unique quadruplets summing to target

Full Transcript

The Four Sum problem finds all unique sets of four numbers in an array that add up to a target sum. We start by sorting the array to make it easier to find quadruplets and skip duplicates. We fix two numbers using two loops (i and j). For each pair, we use two pointers (left and right) to find pairs that complete the quadruplet. We calculate the sum of the four numbers. If the sum equals the target, we add the quadruplet to the result and skip duplicates. If the sum is less than the target, we move the left pointer right to increase the sum. If the sum is greater, we move the right pointer left to decrease the sum. We repeat this until left meets right, then move j and i to the next unique values. This process continues until all quadruplets are found. Skipping duplicates ensures no repeated quadruplets. The final result is a list of all unique quadruplets that sum to the target.