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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Four Sum Unique Quadruplets Function

What is the output of the following Python function when called with nums = [1, 0, -1, 0, -2, 2] and target = 0?

DSA Python

def four_sum(nums, target):
    nums.sort()
    quadruplets = []
    n = len(nums)
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            left, right = j + 1, n - 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
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
                elif total < target:
                    left += 1
                else:
                    right -= 1
    return quadruplets

result = four_sum([1, 0, -1, 0, -2, 2], 0)
print(result)

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

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

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

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

💡 Hint

Think about sorting and skipping duplicates to find unique quadruplets.

The function sorts the array and uses two nested loops with two pointers to find all unique quadruplets that sum to the target. It skips duplicates to avoid repeated quadruplets.

🧠 Conceptual

intermediate

Number of Unique Quadruplets for Four Sum

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

A 1

B 5

C 0

D 10

💡 Hint

All elements are the same, so quadruplets must be identical.

Only one unique quadruplet [2, 2, 2, 2] sums to 8, duplicates are skipped.

🔧 Debug

advanced

Identify the Error in Four Sum Implementation

What error will occur when running this code snippet for four sum?

DSA Python

def four_sum_bug(nums, target):
    nums.sort()
    quadruplets = []
    n = len(nums)
    for i in range(n - 3):
        for j in range(i + 1, n - 2):
            left, right = j + 1, n - 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
    return quadruplets

print(four_sum_bug([1, 0, -1, 0, -2, 2], 0))

A IndexError due to out of range access

B No error, but duplicates quadruplets will appear

C TypeError because of wrong data type

D SyntaxError due to missing colon

💡 Hint

Check if duplicates are handled in the loops.

The code lacks checks to skip duplicate values for i and j, so duplicate quadruplets appear but no runtime error occurs.

🚀 Application

advanced

Find Quadruplets Summing to Target in Large Array

Given nums = [1, 0, -1, 0, -2, 2, 2, -1, -4] and target = 0, which of the following lists contains all unique quadruplets returned by the four sum algorithm?

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

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

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

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

💡 Hint

Sort the array and carefully find quadruplets summing to zero without duplicates.

Option D correctly lists all unique quadruplets summing to zero from the given array after sorting and skipping duplicates.

🧠 Conceptual

expert

Time Complexity of Four Sum Algorithm

What is the time complexity of the standard four sum algorithm that finds all unique quadruplets in an array of length n?

A O(n^2)

B O(n log n)

C O(n^3)

D O(n^4)

💡 Hint

Consider nested loops and two-pointer approach inside.

The algorithm uses two nested loops and a two-pointer scan inside, resulting in O(n^3) time complexity.

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