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.

Practice

1. What is the main goal of the Four Sum Problem in data structures and algorithms?

easy

A. Find all unique quadruplets in an array that sum up to a target value

B. Sort the array in ascending order

C. Find the maximum element in the array

D. Count the number of pairs that sum to a target

Solution

1. Step 1: Understand the problem statement

   The Four Sum Problem asks to find all unique sets of four numbers (quadruplets) in an array that add up to a given target sum.

2. Step 2: Identify the goal

   The goal is not sorting or counting pairs but to find quadruplets with a specific sum without duplicates.

3. Final Answer:

   Find all unique quadruplets in an array that sum up to a target value -> Option A

4. Quick Check:

   Four Sum = unique quadruplets summing to target [OK]

Hint: Look for four numbers adding to target, no duplicates [OK]

Common Mistakes:

• Confusing Four Sum with Two Sum or Three Sum problems
• Thinking the problem is about sorting or counting pairs
• Ignoring the uniqueness of quadruplets

2. Which of the following Python code snippets correctly initializes an empty list to store quadruplets for the Four Sum problem?

easy

A. quadruplets = ()

B. quadruplets = []

C. quadruplets = {}

D. quadruplets = set()

Solution

1. Step 1: Identify the correct data structure for storing multiple quadruplets

   Quadruplets are multiple groups of four numbers, so a list is suitable to store them.

2. Step 2: Check the initialization syntax

   Using [] initializes an empty list, which is correct. Curly braces {} create a dictionary, parentheses () create a tuple, and set() creates a set which is unordered and not ideal here.

3. Final Answer:

   quadruplets = [] -> Option B

4. Quick Check:

   Empty list for quadruplets = [] [OK]

Hint: Use [] to store multiple quadruplets in a list [OK]

Common Mistakes:

• Using {} which creates a dictionary, not a list
• Using () which creates an immutable tuple
• Using set() which is unordered and may lose duplicates

3. What will be the output of the following Python code snippet for the Four Sum problem?

nums = [1, 0, -1, 0, -2, 2]
target = 0
# After sorting
nums.sort()
quadruplets = []
for i in range(len(nums)-3):
    for j in range(i+1, len(nums)-2):
        left, right = j+1, len(nums)-1
        while left < right:
            total = nums[i] + nums[j] + nums[left] + nums[right]
            if total == target:
                quadruplets.append([nums[i], nums[j], nums[left], nums[right]])
                left += 1
                right -= 1
            elif total < target:
                left += 1
            else:
                right -= 1
print(quadruplets)

medium

A. [[-2, -1, 0, 1], [-1, 0, 0, 1]]

B. [[1, 0, -1, 0], [-2, 2, -1, 1]]

C. [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

D. []

Solution

1. Step 1: Sort the array and understand the loops

   Sorted nums = [-2, -1, 0, 0, 1, 2]. The nested loops and two-pointer approach check all quadruplets summing to target 0.

2. Step 2: Identify quadruplets that sum to zero

   Valid quadruplets are [-2, -1, 1, 2], [-2, 0, 0, 2], and [-1, 0, 0, 1]. These are appended to quadruplets list.

3. Final Answer:

   [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] -> Option C

4. Quick Check:

   Sum quadruplets = 0 matches output [OK]

Hint: Sort array, use two pointers inside nested loops [OK]

Common Mistakes:

• Not sorting the array before processing
• Missing some quadruplets due to pointer errors
• Appending duplicates without checks

4. Identify the bug in the following code snippet for the Four Sum problem and select the correct fix.

nums = [2, 2, 2, 2, 2]
target = 8
nums.sort()
quadruplets = []
for i in range(len(nums)-3):
    for j in range(i+1, len(nums)-2):
        left, right = j+1, len(nums)-1
        while left < right:
            total = nums[i] + nums[j] + nums[left] + nums[right]
            if total == target:
                quadruplets.append([nums[i], nums[j], nums[left], nums[right]])
                left += 1
                right -= 1
            elif total < target:
                left += 1
            else:
                right -= 1
print(quadruplets)

medium

A. Add checks to skip duplicates for i, j, left, and right indices

B. Change quadruplets to a set to avoid duplicates

C. Remove sorting to improve performance

D. Replace while loop with a for loop

Solution

1. Step 1: Identify the problem with duplicates

   The code appends quadruplets but does not skip duplicates, so it will add the same quadruplet multiple times.

2. Step 2: Fix by skipping duplicates

   Adding checks to skip duplicate values for i, j, left, and right indices after finding a quadruplet prevents repeated quadruplets.

3. Final Answer:

   Add checks to skip duplicates for i, j, left, and right indices -> Option A

4. Quick Check:

   Skipping duplicates avoids repeated quadruplets [OK]

Hint: Skip duplicates after finding quadruplets to avoid repeats [OK]

Common Mistakes:

• Not skipping duplicates causing repeated quadruplets
• Using set without sorting can cause unordered results
• Removing sorting breaks two-pointer logic

5. Given the array nums = [1, 0, -1, 0, -2, 2, 2] and target 2, which of the following lists contains all unique quadruplets that sum to the target?

hard

A. [[-2, -1, 2, 3], [0, 0, 1, 1]]

B. [[-2, 0, 1, 3], [-1, 0, 0, 3]]

C. [[1, 0, 0, 1], [-2, -1, 2, 3]]

D. [[-2, 0, 2, 2], [-1, 0, 1, 2]]

Solution

1. Step 1: Sort the array and find quadruplets summing to 2

   Sorted nums = [-2, -1, 0, 0, 1, 2, 2]. We look for quadruplets where sum equals 2.

2. Step 2: Identify valid quadruplets

   Valid quadruplets are [-2, 0, 2, 2] (sum = 2) and [-1, 0, 1, 2] (sum = 2). Other options contain invalid or impossible sums.

3. Final Answer:

   [[-2, 0, 2, 2], [-1, 0, 1, 2]] -> Option D

4. Quick Check:

   Sum quadruplets = 2 matches output [OK]

Hint: Sort and check quadruplets summing exactly to target [OK]

Common Mistakes:

• Including quadruplets with wrong sums
• Ignoring duplicates or invalid numbers
• Not sorting before searching quadruplets