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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Four Sum Unique Quadruplets Function

What is the output of the following code that finds all unique quadruplets in the array that sum to the target 0?

DSA C

void fourSum(int* nums, int numsSize, int target) {
    // Assume nums is sorted
    for (int i = 0; i < numsSize - 3; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        for (int j = i + 1; j < numsSize - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j-1]) continue;
            int left = j + 1, right = numsSize - 1;
            while (left < right) {
                int sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    printf("[%d, %d, %d, %d]\n", nums[i], nums[j], nums[left], nums[right]);
                    while (left < right && nums[left] == nums[left+1]) left++;
                    while (left < right && nums[right] == nums[right-1]) right--;
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
}

int main() {
    int nums[] = {1, 0, -1, 0, -2, 2};
    int size = sizeof(nums)/sizeof(nums[0]);
    // Sort the array
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (nums[j] > nums[j+1]) {
                int temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
            }
        }
    }
    fourSum(nums, size, 0);
    return 0;
}

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

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

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

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

💡 Hint

Remember to sort the array first and skip duplicates to get unique quadruplets.

The code sorts the array and uses two nested loops with two pointers to find quadruplets summing to zero. It skips duplicates to ensure unique quadruplets. The correct quadruplets are [-2, -1, 1, 2], [-2, 0, 0, 2], and [-1, 0, 0, 1].

🧠 Conceptual

intermediate

Understanding the Role of Sorting in Four Sum

Why is sorting the array important before finding all unique quadruplets that sum to a target?

A Sorting is not necessary; it only makes the code run slower.

B Sorting helps to easily skip duplicate elements and use two pointers efficiently.

C Sorting changes the target sum to zero automatically.

D Sorting removes negative numbers from the array.

💡 Hint

Think about how duplicates and two pointers work.

Sorting allows the algorithm to skip duplicates easily by comparing adjacent elements and enables the two-pointer technique to find pairs efficiently.

🔧 Debug

advanced

Identify the Bug in Quadruplet Finding Code

What error will occur if the inner while loops that skip duplicates are removed from the four sum code?

DSA C

while (left < right) {
    int sum = nums[i] + nums[j] + nums[left] + nums[right];
    if (sum == target) {
        printf("[%d, %d, %d, %d]\n", nums[i], nums[j], nums[left], nums[right]);
        // Duplicate skipping loops removed here
        left++;
        right--;
    } else if (sum < target) {
        left++;
    } else {
        right--;
    }
}

A The code will miss some quadruplets that sum to the target.

B The code will cause a segmentation fault.

C The code will not compile due to syntax errors.

D The code will print duplicate quadruplets multiple times.

💡 Hint

Think about what skipping duplicates prevents.

Without skipping duplicates, the same quadruplet can be printed multiple times because the pointers move without checking for repeated values.

❓ Predict Output

advanced

Output with Negative Target Sum

What is the output of the four sum function when the input array is [-3, -1, 0, 2, 4, 5] and the target is 2?

DSA C

int nums[] = {-3, -1, 0, 2, 4, 5};
int size = sizeof(nums)/sizeof(nums[0]);
// Sort the array
for (int i = 0; i < size - 1; i++) {
    for (int j = 0; j < size - i - 1; j++) {
        if (nums[j] > nums[j+1]) {
            int temp = nums[j];
            nums[j] = nums[j+1];
            nums[j+1] = temp;
        }
    }
}
fourSum(nums, size, 2);

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

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

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

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

💡 Hint

Check sums carefully and remember the array is sorted.

Only the quadruplet [-3, -1, 2, 4] sums to 2. Other options include numbers not in the array or sums that don't match.

🧠 Conceptual

expert

Time Complexity of Four Sum Algorithm

What is the time complexity of the standard four sum algorithm that uses sorting and two pointers to find all unique quadruplets?

A O(n^3)

B O(n^4)

C O(n^2 log n)

D O(n^2)

💡 Hint

Consider the nested loops and two-pointer approach.

The algorithm uses two nested loops (O(n^2)) and inside uses two pointers moving linearly (O(n)), resulting in O(n^3) time complexity.