Four Sum Problem All Unique Quadruplets in DSA Go

Mental Model

Find four numbers in a list that add up to a target without repeating the same group twice.

Analogy: Imagine picking four different fruits from a basket so their total weight matches a specific number, and you never pick the same combination twice.

Array: [1, 0, -1, 0, -2, 2]
Indices:  0  1   2  3   4   5
Goal: Find quadruplets that sum to 0

Dry Run Walkthrough

Input: list: [1, 0, -1, 0, -2, 2], target: 0

Goal: Find all unique sets of four numbers that add up to 0

Step 1: Sort the array to make it easier to avoid duplicates and use two pointers

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

Why: Sorting helps to skip duplicates and use two-pointer technique efficiently

Step 2: Fix first number at index 0 (-2), then fix second number at index 1 (-1)

First: -2, Second: -1, Remaining: [0, 0, 1, 2]

Why: We pick first two numbers and look for two others to complete quadruplet

Step 3: Use two pointers: left at index 2 (0), right at index 5 (2), sum = -2 + -1 + 0 + 2 = -1

-1 < 0, move left pointer right to increase sum

Why: Sum less than target, so move left pointer to get bigger sum

Step 4: Left pointer moves to index 3 (0), sum = -2 + -1 + 0 + 2 = -1 again

Still less than target, move left pointer right

Why: Try next number to increase sum

Step 5: Left pointer moves to index 4 (1), sum = -2 + -1 + 1 + 2 = 0

Sum equals target, record quadruplet [-2, -1, 1, 2]

Why: Found one quadruplet that matches target

Step 6: Move left pointer right and right pointer left to avoid duplicates and find other quadruplets

Left at 5, right at 4, pointers cross, end this pair

Why: No more pairs with first two fixed numbers

Step 7: Fix first number at index 0 (-2), second number at index 2 (0), two pointers at 3 (0) and 5 (2)

Sum = -2 + 0 + 0 + 2 = 0, record quadruplet [-2, 0, 0, 2]

Why: Found another quadruplet

Step 8: Continue fixing first and second numbers and searching pairs similarly, skipping duplicates

Also find quadruplet [-1, 0, 0, 1]

Why: Complete search for all unique quadruplets

Result:

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

Annotated Code

DSA Go

package main

import (
	"fmt"
	"sort"
)

func fourSum(nums []int, target int) [][]int {
	sort.Ints(nums) // sort array to use two pointers and skip duplicates
	result := [][]int{}
	n := len(nums)

	for i := 0; i < n-3; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue // skip duplicate first number
		}
		for j := i + 1; j < n-2; j++ {
			if j > i+1 && nums[j] == nums[j-1] {
				continue // skip duplicate second number
			}
			left, right := j+1, n-1
			for left < right {
				sum := nums[i] + nums[j] + nums[left] + nums[right]
				if sum == target {
					result = append(result, []int{nums[i], nums[j], nums[left], nums[right]})
					// skip duplicates for left
					for left < right && nums[left] == nums[left+1] {
						left++
					}
					// skip duplicates for right
					for left < right && nums[right] == nums[right-1] {
						right--
					}
					left++
					right--
				} else if sum < target {
					left++ // increase sum by moving left pointer right
				} else {
					right-- // decrease sum by moving right pointer left
				}
			}
		}
	}
	return result
}

func main() {
	nums := []int{1, 0, -1, 0, -2, 2}
	target := 0
	quadruplets := fourSum(nums, target)
	for _, quad := range quadruplets {
		fmt.Println(quad)
	}
}

sort.Ints(nums) // sort array to use two pointers and skip duplicates

sort array to enable two-pointer technique and duplicate skipping

if i > 0 && nums[i] == nums[i-1] { continue }

skip duplicate first numbers to avoid repeated quadruplets

if j > i+1 && nums[j] == nums[j-1] { continue }

skip duplicate second numbers to avoid repeated quadruplets

for left < right { sum := nums[i] + nums[j] + nums[left] + nums[right] ... }

use two pointers to find pairs that complete quadruplet sum

if sum == target { append quadruplet; skip duplicates for left and right; move pointers }

record quadruplet and move pointers skipping duplicates

else if sum < target { left++ } else { right-- }

adjust pointers to increase or decrease sum towards target

Output

[-2 -1 1 2]

[-2 0 0 2]

[-1 0 0 1]

Complexity Analysis

Time: O(n^3) because we use three nested loops and two pointers inside the innermost loop

Space: O(k) where k is number of quadruplets found, for storing results

vs Alternative: Naive approach is O(n^4) by checking all quadruplets; this method is faster by sorting and using two pointers

Edge Cases

Empty array

Returns empty list, no quadruplets found

DSA Go

for i := 0; i < n-3; i++ {

Array with fewer than 4 elements

Returns empty list, no quadruplets possible

DSA Go

for i := 0; i < n-3; i++ {

All elements are the same and sum matches target

Returns one quadruplet with those elements, duplicates skipped

DSA Go

if i > 0 && nums[i] == nums[i-1] { continue }

When to Use This Pattern

When asked to find unique quadruplets summing to a target, use sorting plus two nested loops and two pointers to efficiently find all sets without duplicates.

Common Mistakes

Mistake: Not sorting the array first, causing difficulty in skipping duplicates and using two pointers
Fix: Always sort the array before processing quadruplets

Mistake: Not skipping duplicates for first and second numbers, leading to repeated quadruplets
Fix: Add checks to skip duplicates for i and j indices

Mistake: Not skipping duplicates for left and right pointers after finding a quadruplet
Fix: After recording quadruplet, move left and right pointers skipping duplicates

Summary

Finds all unique sets of four numbers that add up to a target sum.

Use when you need to find quadruplets in an array that sum to a specific value without repeats.

Sort the array and use two nested loops plus two pointers to efficiently find quadruplets and skip 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