Four Sum Problem All Unique Quadruplets in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to sort the input list before processing.

DSA Python

nums = [1, 0, -1, 0, -2, 2]
nums.[1]()

Drag options to blanks, or click blank then click option'

Asort

Breverse

Cappend

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using reverse() instead of sort()

Trying to append or pop elements here

Sorting the list helps to efficiently find quadruplets and avoid duplicates.

2fill in blank

medium

Complete the code to skip duplicate values for the first pointer i.

DSA Python

for i in range(len(nums) - 3):
    if i > 0 and nums[i] == nums[[1]]:
        continue

Drag options to blanks, or click blank then click option'

A0

Bi + 1

Ci - 1

Dlen(nums)

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with i + 1 which is the next element

Comparing with 0 index always

To skip duplicates, compare current element with the previous one at i-1.

3fill in blank

hard

Fix the error in the while loop condition to avoid infinite loops.

DSA Python

while left < right:
    total = nums[i] + nums[j] + nums[left] + nums[right]
    if total == target:
        result.append([nums[i], nums[j], nums[left], nums[right]])
        left += 1
        right -= 1
        while left < right and nums[left] == nums[[1]]:
            left += 1

Drag options to blanks, or click blank then click option'

Aleft - 1

Bleft + 1

Cright + 1

Dright - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using left + 1 which causes skipping too far

Using right pointers incorrectly

We compare nums[left] with the previous left value at left - 1 to skip duplicates.

4fill in blank

hard

Fill both blanks to skip duplicates for the second pointer j.

DSA Python

for j in range(i + 1, len(nums) - 2):
    if j > i + 1 and nums[j] == nums[[1]]:
        continue
    left, right = j + 1, len(nums) - 1
    while left < right:
        # code to find quadruplets
        if total == target:
            # after adding quadruplet
            while left < right and nums[right] == nums[[2]]:
                right -= 1

Drag options to blanks, or click blank then click option'

Aj - 1

Bj + 1

Cright + 1

Dright - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using j + 1 instead of j - 1 for skipping duplicates

Using right + 1 instead of right - 1 for skipping duplicates

To skip duplicates for j, compare with previous j-1; for right pointer, compare with right-1.

5fill in blank

hard

Fill all three blanks to complete the dictionary comprehension that counts quadruplets by their sum.

DSA Python

quadruplet_sums = { [1]: [2] for quad in quadruplets if sum(quad) [3] target }

Drag options to blanks, or click blank then click option'

Asum(quad)

Bquad

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '!=' instead of '==' in the condition

Swapping key and value in the dictionary comprehension

We create a dictionary with sum(quad) as key and quad as value, filtering sums equal to 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