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.