Three Sum Problem All Unique Triplets in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Three Sum Unique Triplets Function

What is the output of the following C function when called with nums = [-1, 0, 1, 2, -1, -4] and numsSize = 6?

DSA C

/* Returns number of triplets found, stores triplets in result array */
int threeSum(int* nums, int numsSize, int*** result) {
    int capacity = 16, count = 0;
    *result = malloc(capacity * sizeof(int*));
    for (int i = 0; i < numsSize - 2; i++) {
        for (int j = i + 1; j < numsSize - 1; j++) {
            for (int k = j + 1; k < numsSize; k++) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    int triplet[3] = {nums[i], nums[j], nums[k]};
                    // Sort triplet
                    for (int a = 0; a < 2; a++) {
                        for (int b = a + 1; b < 3; b++) {
                            if (triplet[a] > triplet[b]) {
                                int temp = triplet[a];
                                triplet[a] = triplet[b];
                                triplet[b] = temp;
                            }
                        }
                    }
                    // Check for duplicates
                    int duplicate = 0;
                    for (int x = 0; x < count; x++) {
                        if ((*result)[x][0] == triplet[0] && (*result)[x][1] == triplet[1] && (*result)[x][2] == triplet[2]) {
                            duplicate = 1;
                            break;
                        }
                    }
                    if (!duplicate) {
                        if (count == capacity) {
                            capacity *= 2;
                            *result = realloc(*result, capacity * sizeof(int*));
                        }
                        (*result)[count] = malloc(3 * sizeof(int));
                        (*result)[count][0] = triplet[0];
                        (*result)[count][1] = triplet[1];
                        (*result)[count][2] = triplet[2];
                        count++;
                    }
                }
            }
        }
    }
    return count;
}

// Example call and print function omitted for brevity

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

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

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

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

💡 Hint

Think about all unique triplets that sum to zero and how duplicates are avoided.

The function finds all unique triplets in the array that sum to zero. The triplets [-1, -1, 2] and [-1, 0, 1] are the only unique sets that satisfy this condition.

🧠 Conceptual

intermediate

Understanding the Time Complexity of Three Sum

What is the time complexity of the naive three sum approach that checks all triplets in an array of size n?

A O(n)

B O(n^3)

C O(n^2)

D O(n log n)

💡 Hint

Consider how many triplets are checked by three nested loops.

The naive approach uses three nested loops each running up to n, resulting in O(n^3) time complexity.

🔧 Debug

advanced

Identify the Bug in Three Sum Duplicate Check

What is the bug in the following duplicate check code snippet inside the three sum function? for (int x = 0; x < count; x++) { if ((*result)[x][0] == triplet[0] && (*result)[x][1] == triplet[1] && (*result)[x][2] == triplet[2]) { duplicate = 1; break; } } Options:

A It does not sort the triplet before checking duplicates, so order mismatch causes misses.

B It compares pointers instead of values, causing false negatives.

C It only checks the first element of triplets, missing duplicates.

D It uses an uninitialized variable 'duplicate' causing undefined behavior.

💡 Hint

Think about how triplets are stored and compared for duplicates.

Triplets must be sorted before duplicate checking to ensure order does not affect equality checks.

❓ Predict Output

advanced

Output of Optimized Three Sum Using Sorting and Two Pointers

What is the output of the following code snippet when nums = [-2, 0, 1, 1, 2]? int nums[] = {-2, 0, 1, 1, 2}; int numsSize = 5; // Assume function threeSumOptimized returns unique triplets sorted internally // and prints them in format: [a, b, c] // Output shown below options

DSA C

void printTriplets(int** triplets, int count) {
    for (int i = 0; i < count; i++) {
        printf("[%d, %d, %d]\n", triplets[i][0], triplets[i][1], triplets[i][2]);
    }
}

// threeSumOptimized implementation omitted for brevity

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

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

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

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

💡 Hint

Think about pairs that sum with a number to zero and unique triplets.

The unique triplets that sum to zero are [-2, 0, 2] and [-2, 1, 1].

🚀 Application

expert

Number of Unique Triplets Summing to Zero

Given the array nums = [3, -1, -7, 2, -2, 1, 5, -3], how many unique triplets exist that sum to zero?

A 4

B 6

C 5

D 3

💡 Hint

Try to find all sets of three numbers that add to zero without duplicates.

The unique triplets are [-7, 2, 5], [-3, -2, 5], [-3, 1, 2], [-2, -1, 3]. There are 4 unique triplets that sum to zero.

Practice

1. What is the main goal of the Three Sum Problem in data structures and algorithms?

easy

A. Find the maximum sum of any three elements

B. Sort the array in ascending order

C. Count the number of pairs that sum to zero

D. Find all unique triplets in an array that sum to zero

Solution

1. Step 1: Understand the problem statement

   The Three Sum Problem asks to find all unique sets of three numbers in an array whose sum is zero.

2. Step 2: Differentiate from other options

   Options A, B, and D describe different problems like maximum sum, sorting, or pairs, not triplets summing to zero.

3. Final Answer:

   Find all unique triplets in an array that sum to zero -> Option D

4. Quick Check:

   Three Sum Problem = Find triplets summing to zero [OK]

Hint: Remember: Three Sum finds triplets with zero sum [OK]

Common Mistakes:

• Confusing with pair sum problems
• Thinking it finds maximum sums
• Assuming it sorts the array only

2. Which of the following code snippets correctly initializes the array for solving the Three Sum Problem in C?

easy

A. int nums[] = { -1, 0, 1, 2, -1, -4 }; int size = sizeof(nums) / sizeof(nums[0]);

B. int nums = { -1, 0, 1, 2, -1, -4 }; int size = 6;

C. int nums[] = (-1, 0, 1, 2, -1, -4); int size = 6;

D. int nums[] = [-1, 0, 1, 2, -1, -4]; int size = 6;

Solution

1. Step 1: Check array initialization syntax in C

   In C, arrays are initialized with curly braces {}, not parentheses or square brackets.

2. Step 2: Verify size calculation

   int nums[] = { -1, 0, 1, 2, -1, -4 }; int size = sizeof(nums) / sizeof(nums[0]); correctly calculates size using sizeof operator divided by element size.

3. Final Answer:

   int nums[] = { -1, 0, 1, 2, -1, -4 }; int size = sizeof(nums) / sizeof(nums[0]); -> Option A

4. Quick Check:

   C array init with {} and sizeof = int nums[] = { -1, 0, 1, 2, -1, -4 }; int size = sizeof(nums) / sizeof(nums[0]); [OK]

Hint: Use curly braces {} for arrays in C [OK]

Common Mistakes:

• Using parentheses () instead of braces {}
• Using square brackets [] for initialization
• Not calculating size correctly

3. What will be the output of the following C code snippet that attempts to find unique triplets summing to zero?

int nums[] = {-1, 0, 1, 2, -1, -4};
int size = 6;
// Assume function threeSum prints triplets
threeSum(nums, size);
// Output format: each triplet printed as (a, b, c)

medium

A. No triplets found

B. (-4, 2, 2)
(-1, 0, 1)

C. (-1, -1, 2)
(-1, 0, 1)

D. (0, 0, 0)
(-1, 1, 2)

Solution

1. Step 1: Identify triplets that sum to zero

   From the array {-1, 0, 1, 2, -1, -4}, the unique triplets summing to zero are (-1, -1, 2) and (-1, 0, 1).

2. Step 2: Verify output matches these triplets

   (-1, -1, 2) (-1, 0, 1) lists these exact triplets; other options include invalid or non-existent triplets.

3. Final Answer:

   (-1, -1, 2) (-1, 0, 1) -> Option C

4. Quick Check:

   Unique triplets summing zero = (-1, -1, 2) (-1, 0, 1) [OK]

Hint: Check sums of triplets carefully for zero [OK]

Common Mistakes:

• Including duplicates like (-4, 2, 2)
• Assuming zero triplets when some exist
• Mixing up triplet elements

4. Identify the bug in the following C code snippet for the Three Sum Problem:

void threeSum(int* nums, int size) {
    for (int i = 0; i < size - 2; i++) {
        for (int j = i + 1; j < size - 1; j++) {
            for (int k = j + 1; k < size; k++) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    printf("(%d, %d, %d)\n", nums[i], nums[j], nums[k]);
                }
            }
        }
    }
}

medium

A. Does not avoid printing duplicate triplets

B. Loops have incorrect ranges causing out-of-bounds access

C. Sum condition should be nums[i] * nums[j] * nums[k] == 0

D. Missing return statement in void function

Solution

1. Step 1: Analyze triplet printing logic

   The code prints any triplet summing to zero but does not check for duplicates, so duplicate triplets may print multiple times.

2. Step 2: Check loop ranges and conditions

   Loop ranges are correct and sum condition is correct; void functions do not require return statements.

3. Final Answer:

   Does not avoid printing duplicate triplets -> Option A

4. Quick Check:

   Duplicate triplets not filtered = Does not avoid printing duplicate triplets [OK]

Hint: Check if duplicates are filtered in nested loops [OK]

Common Mistakes:

• Confusing sum with product condition
• Thinking void needs return
• Assuming loops cause out-of-bounds

5. Given the array int nums[] = {0, 0, 0, 0}; and size 4, what is the correct output of a Three Sum solution that finds all unique triplets summing to zero?

hard

A. No triplets found

B. (0, 0, 0)

C. (0, 0, 0)
(0, 0, 0)

D. (0, 0, 0)
(0, 0, 0)
(0, 0, 0)

Solution

1. Step 1: Identify unique triplets summing to zero

   All elements are zero, so the only unique triplet is (0, 0, 0).

2. Step 2: Avoid duplicates in output

   Even though multiple combinations exist, only one unique triplet should be printed.

3. Final Answer:

   (0, 0, 0) -> Option B

4. Quick Check:

   Unique triplet from zeros = (0, 0, 0) [OK]

Hint: Only print unique triplets, even if duplicates exist [OK]

Common Mistakes:

• Printing duplicate triplets multiple times
• Assuming no triplets because all zeros
• Confusing triplet uniqueness