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

Concept Flow - Four Sum Problem All Unique Quadruplets

Sort the array

↓

Fix first element i

↓

Fix second element j

↓

Use two pointers: left, right

↓

Check sum of nums[i

↓

Skip duplicates

↓

Repeat until all quadruplets found

↓

Return list of unique quadruplets

The algorithm sorts the array, then uses two nested loops to fix the first two numbers, and two pointers to find pairs that complete quadruplets summing to the target, skipping duplicates to ensure uniqueness.

Execution Sample

DSA Go

nums := []int{1, 0, -1, 0, -2, 2}
target := 0
// Find all unique quadruplets that sum to target
// Output quadruplets in ascending order

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

Execution Table

Step	Operation	Indices (i,j,left,right)	Sum	Action	Quadruplets Found	Visual State (Sorted Array)
1	Sort array	-	-	-	[]	[-2, -1, 0, 0, 1, 2]
2	Fix i	i=0	-	-	[]	[-2, -1, 0, 0, 1, 2]
3	Fix j	i=0, j=1	-	-	[]	[-2, -1, 0, 0, 1, 2]
4	Set pointers	i=0, j=1, left=2, right=5	-	-	[]	[-2, -1, 0, 0, 1, 2]
5	Calculate sum	0,1,2,5	-2 + -1 + 0 + 2 = -1	Sum < target, move left++	[]	[-2, -1, 0, 0, 1, 2]
6	Calculate sum	0,1,3,5	-2 + -1 + 0 + 2 = -1	Sum < target, move left++	[]	[-2, -1, 0, 0, 1, 2]
7	Calculate sum	0,1,4,5	-2 + -1 + 1 + 2 = 0	Sum == target, add quadruplet [-2,-1,1,2], move left++, right--	[[-2,-1,1,2]]	[-2, -1, 0, 0, 1, 2]
8	Move pointers	0,1,5,4	left > right, end inner loop	-	[[-2,-1,1,2]]	[-2, -1, 0, 0, 1, 2]
9	Fix j	i=0, j=2	-	-	[[-2,-1,1,2]]	[-2, -1, 0, 0, 1, 2]
10	Set pointers	0,2,3,5	-	-	[[-2,-1,1,2]]	[-2, -1, 0, 0, 1, 2]
11	Calculate sum	0,2,3,5	-2 + 0 + 0 + 2 = 0	Sum == target, add quadruplet [-2,0,0,2], move left++, right--	[[-2,-1,1,2],[-2,0,0,2]]	[-2, -1, 0, 0, 1, 2]
12	Move pointers	0,2,4,4	left == right, end inner loop	-	[[-2,-1,1,2],[-2,0,0,2]]	[-2, -1, 0, 0, 1, 2]
13	Fix j	i=0, j=3	Skip duplicate j (nums[3] == nums[2])	-	[[-2,-1,1,2],[-2,0,0,2]]	[-2, -1, 0, 0, 1, 2]
14	Fix i	i=1	-	-	[[-2,-1,1,2],[-2,0,0,2]]	[-2, -1, 0, 0, 1, 2]
15	Fix j	i=1, j=2	-	-	[[-2,-1,1,2],[-2,0,0,2]]	[-2, -1, 0, 0, 1, 2]
16	Set pointers	1,2,3,5	-	-	[[-2,-1,1,2],[-2,0,0,2]]	[-2, -1, 0, 0, 1, 2]
17	Calculate sum	1,2,3,5	-1 + 0 + 0 + 2 = 1	Sum > target, move right--	[[-2,-1,1,2],[-2,0,0,2]]	[-2, -1, 0, 0, 1, 2]
18	Calculate sum	1,2,3,4	-1 + 0 + 0 + 1 = 0	Sum == target, add quadruplet [-1,0,0,1], move left++, right--	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	[-2, -1, 0, 0, 1, 2]
19	Move pointers	1,2,4,3	left > right, end inner loop	-	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	[-2, -1, 0, 0, 1, 2]
20	Fix j	i=1, j=3	Skip duplicate j (nums[3] == nums[2])	-	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	[-2, -1, 0, 0, 1, 2]
21	Fix i	i=2	-	-	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	[-2, -1, 0, 0, 1, 2]
22	Fix j	i=2, j=3	-	-	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	[-2, -1, 0, 0, 1, 2]
23	Set pointers	2,3,4,5	-	-	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	[-2, -1, 0, 0, 1, 2]
24	Calculate sum	2,3,4,5	0 + 0 + 1 + 2 = 3	Sum > target, move right--	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	[-2, -1, 0, 0, 1, 2]
25	Calculate sum	2,3,4,4	left == right, end inner loop	-	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	[-2, -1, 0, 0, 1, 2]
26	Fix j	i=2, j=4	j > length-2, end j loop	-	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	[-2, -1, 0, 0, 1, 2]
27	Fix i	i=3	i > length-3, end i loop	-	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	[-2, -1, 0, 0, 1, 2]

💡 All quadruplets found or loops exhausted

Variable Tracker

Variable	Start	After Step 2	After Step 9	After Step 14	After Step 21	Final
i	-	0	0	1	2	3
j	-	1	2	2	3	4
left	-	-	2	3	4	-
right	-	-	5	5	5	-
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 duplicate values for j and left pointers?

Skipping duplicates prevents adding the same quadruplet multiple times. For example, at step 13 and 20, we skip j when nums[j] equals the previous to avoid repeated quadruplets, as shown in the execution_table.

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 5-6 and 17-18.

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

When left meets or passes right, all pairs for fixed i and j are checked. Continuing would repeat or invalid pairs. This is shown in steps 8, 12, 19, 25.

Visual Quiz - 3 Questions

Look at the execution_table at step 7. What quadruplet is added?

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

B [-2, 0, 0, 2]

C [-1, 0, 0, 1]

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

💡 Hint

Check the 'Quadruplets Found' column at step 7 in execution_table.

At which step does the sum first equal the target 0?

A Step 5

B Step 7

C Step 11

D Step 18

💡 Hint

Look at the 'Sum' and 'Action' columns in execution_table to find when sum == target first occurs.

If the array had no duplicates, which step would be skipped?

A Step 13

B Step 14

C Step 20

D Step 25

💡 Hint

Check steps where duplicate skipping is mentioned in the 'Operation' column of execution_table.

Concept Snapshot

Four Sum Problem:
- Sort the array first
- Use two loops to fix first two numbers (i, j)
- Use two pointers (left, right) to find pairs
- Move pointers based on sum compared to target
- Skip duplicates to ensure unique quadruplets
- Return all unique quadruplets found

Full Transcript

The Four Sum problem finds all unique sets of four numbers in an array that add up to a target sum. The approach starts by sorting the array to make it easier to avoid duplicates and use two pointers effectively. We fix the first two numbers using nested loops, then use two pointers to find the remaining two numbers that complete the quadruplet. We calculate the sum of these four numbers and compare it to the target. 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. When the sum equals the target, we add the quadruplet to the result and move both pointers, skipping duplicates to avoid repeated quadruplets. This process continues until all quadruplets are found or the loops finish. The execution table shows each step, pointer positions, sums, and quadruplets found, helping visualize how the algorithm progresses and avoids duplicates.

Practice

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

easy

A. Sort the array in ascending order

B. Count the number of pairs with a given sum

C. Find the maximum element in the array

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

Solution

1. Step 1: Understand the problem statement

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

2. Step 2: Identify the goal

   The goal is not sorting or counting pairs but to find quadruplets that sum to the target without duplicates.

3. Final Answer:

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

4. Quick Check:

   Four Sum Problem = Find quadruplets summing to target [OK]

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

Common Mistakes:

• Confusing with two or three sum problems
• Trying to sort only without finding quadruplets
• Counting pairs instead of quadruplets

2. Which of the following Go code snippets correctly initializes a slice to store quadruplets for the Four Sum problem?

easy

A. quadruplets := [][]int{}

B. quadruplets := [4]int{}

C. quadruplets := make([]int, 4)

D. quadruplets := map[int]int{}

Solution

1. Step 1: Understand data structure for quadruplets

   We need a slice of slices of integers to store multiple quadruplets, each quadruplet is a slice of 4 ints.

2. Step 2: Choose correct initialization

   quadruplets := [][]int{} initializes an empty slice of int slices, suitable for storing multiple quadruplets. quadruplets := [4]int{} is a fixed array of 4 ints, not multiple quadruplets. quadruplets := make([]int, 4) is a slice of 4 ints, not a slice of quadruplets. quadruplets := map[int]int{} is a map, not suitable here.

3. Final Answer:

   quadruplets := [][]int{} -> Option A

4. Quick Check:

   Slice of int slices = [][]int{} [OK]

Hint: Use [][]int{} for list of quadruplets [OK]

Common Mistakes:

• Using fixed arrays instead of slices
• Using map instead of slice
• Initializing slice with wrong dimensions

3. What will be the output of the following Go code snippet that finds unique quadruplets summing to 0?

nums := []int{1, 0, -1, 0, -2, 2}
target := 0
result := fourSum(nums, target)
fmt.Println(result)

// Assume fourSum is correctly implemented

medium

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

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

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

D. []

Solution

1. Step 1: Understand input and target

   The input array is [1, 0, -1, 0, -2, 2] and target sum is 0.

2. Step 2: Identify unique quadruplets summing to 0

   Possible unique quadruplets are [-2, -1, 1, 2], [-2, 0, 0, 2], and [-1, 0, 0, 1]. These sum exactly to 0 and are unique.

3. Final Answer:

   [[-2 -1 1 2] [-2 0 0 2] [-1 0 0 1]] -> Option B

4. Quick Check:

   Sum quadruplets = 0 [OK]

Hint: Sort array and find quadruplets summing to target [OK]

Common Mistakes:

• Including duplicate quadruplets
• Incorrect sums in quadruplets
• Missing some valid quadruplets

4. Given the following Go code snippet for the Four Sum problem, what is the main bug causing incorrect results?

func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)
    var res [][]int
    for i := 0; i < len(nums)-3; i++ {
        for j := i + 1; j < len(nums)-2; j++ {
            left, right := j+1, len(nums)-1
            for left < right {
                sum := nums[i] + nums[j] + nums[left] + nums[right]
                if sum == target {
                    res = append(res, []int{nums[i], nums[j], nums[left], nums[right]})
                    left++
                    right--
                } else if sum < target {
                    left++
                } else {
                    right--
                }
            }
        }
    }
    return res
}

medium

A. No checks to skip duplicate quadruplets causing duplicates in result

B. Incorrect sorting of the input array

C. Wrong initialization of left and right pointers

D. Using append incorrectly causing runtime error

Solution

1. Step 1: Analyze duplicate handling

   The code finds quadruplets but does not skip duplicates after finding a valid quadruplet, so duplicates appear in the result.

2. Step 2: Check other parts

   Sorting is correct, pointers are correctly initialized, and append usage is valid.

3. Final Answer:

   No checks to skip duplicate quadruplets causing duplicates in result -> Option A

4. Quick Check:

   Missing duplicate skip = duplicates in output [OK]

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

Common Mistakes:

• Not skipping duplicates for i, j, left, right
• Incorrect pointer updates after finding quadruplet
• Assuming sorting alone removes duplicates

5. You want to optimize the Four Sum solution to avoid unnecessary computations. Which approach best reduces the search space while ensuring all unique quadruplets are found?

hard

A. Sort the array and use two nested loops with two pointers, skipping duplicates at each step

B. Use four nested loops to check all quadruplets without sorting

C. Sort the array and use a hash map to store sums of pairs, then find complements

D. Use recursion without sorting or duplicate checks

Solution

1. Step 1: Understand optimization goals

   We want to reduce time complexity and avoid duplicates efficiently.

2. Step 2: Evaluate approaches

   Sort the array and use two nested loops with two pointers, skipping duplicates at each step is common but still O(n^3). Use four nested loops to check all quadruplets without sorting is brute force O(n^4). Sort the array and use a hash map to store sums of pairs, then find complements uses a hash map to store pair sums and find complements, reducing complexity and handling duplicates well. Use recursion without sorting or duplicate checks is inefficient without sorting or duplicate checks.

3. Final Answer:

   Sort the array and use a hash map to store sums of pairs, then find complements -> Option C

4. Quick Check:

   Hash map pairs + complements = optimized search [OK]

Hint: Use hash map of pair sums to find quadruplets faster [OK]

Common Mistakes:

• Using brute force four loops
• Ignoring duplicate skipping
• Not sorting before processing