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.