Four Sum Problem All Unique Quadruplets in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Four Sum Quadruplets for a Simple Input

What is the output of the following Go code that finds all unique quadruplets summing to target 0?

DSA Go

package main

import (
	"fmt"
	"sort"
)

func fourSum(nums []int, target int) [][]int {
	sort.Ints(nums)
	result := [][]int{}
	n := len(nums)
	for i := 0; i < n-3; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		for j := i + 1; j < n-2; j++ {
			if j > i+1 && nums[j] == nums[j-1] {
				continue
			}
			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]})
					left++
					right--
					for left < right && nums[left] == nums[left-1] {
						left++
					}
					for left < right && nums[right] == nums[right+1] {
						right--
					}
				} else if sum < target {
					left++
				} else {
					right--
				}
			}
		}
	}
	return result
}

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

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

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

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

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

💡 Hint

Think about sorting the array first and then using two pointers to find pairs.

The code sorts the array and uses two nested loops with two pointers to find quadruplets that sum to the target 0. It skips duplicates to ensure unique quadruplets.

🧠 Conceptual

intermediate

Number of Unique Quadruplets for Given Input

Given the input array nums = [2, 2, 2, 2, 2] and target = 8, how many unique quadruplets does the four sum algorithm find?

A 10

B 0

C 1

D 5

💡 Hint

All elements are the same, so quadruplets must use these repeated elements.

Only one unique quadruplet [2, 2, 2, 2] sums to 8. The algorithm skips duplicates, so it counts this quadruplet once.

🔧 Debug

advanced

Identify the Bug in Four Sum Implementation

What error will the following code produce when run, and why? func fourSum(nums []int, target int) [][]int { sort.Ints(nums) result := [][]int{} n := len(nums) for i := 0; i <= n-3; i++ { for j := i + 1; j < n-2; j++ { 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]}) left++ right-- } else if sum < target { left++ } else { right-- } } } } return result }

A Index out of range error because loop condition i <= n-3 allows i to be n-3 which is invalid

B No error, code runs correctly and returns all quadruplets

C Infinite loop because left and right pointers are not updated properly

D Compilation error due to missing import statement

💡 Hint

Check the loop boundary conditions carefully for the outer loop.

The outer loop uses i <= n-3 which allows i to be n-3, but inside the inner loops and pointer usage, this causes index out of range when accessing nums[i+3]. The correct condition is i < n-3.

📝 Syntax

advanced

Correct Syntax for Skipping Duplicates in Four Sum

Which option correctly skips duplicates for the second loop variable j in the four sum algorithm?

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

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

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

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

💡 Hint

The duplicate check for j must ensure it only skips when j is beyond the first iteration after i.

The correct condition is j > i+1 to skip duplicates after the first j for each i. Other options either skip too early or too late.

🚀 Application

expert

Time Complexity of Four Sum Algorithm

What is the time complexity of the standard four sum algorithm that sorts the array and uses two nested loops plus two pointers to find quadruplets?

A O(n^2)

B O(n^2 log n)

C O(n^4)

D O(n^3)

💡 Hint

Consider the loops and the two-pointer approach inside the nested loops.

The algorithm sorts the array in O(n log n), then uses two nested loops (O(n^2)) and inside uses two pointers moving linearly (O(n)), resulting in O(n^3) overall.

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