Three Sum Problem All Unique Triplets in DSA C

Mental Model

Find three numbers in a list that add up to zero without repeating the same triplet.

Analogy: Imagine you have a group of friends with different ages, and you want to find three friends whose ages add up exactly to zero, but you don't want to count the same group twice.

Array: [-4, -1, -1, 0, 1, 2]
Indexes:  0    1    2   3  4  5
Goal: Find triplets i, j, k where arr[i] + arr[j] + arr[k] = 0
Pointers: i ↑, j ->, k ←

Dry Run Walkthrough

Input: array: [-1, 0, 1, 2, -1, -4]

Goal: Find all unique triplets that sum to zero

Step 1: Sort the array

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

Why: Sorting helps to avoid duplicates and use two-pointer technique

Step 2: Set i=0 (value -4), set left=1, right=5

i=-4 ↑, left=-1 ->, right=2 ←

Why: Start checking triplets with first element -4

Step 3: Sum = -4 + (-1) + 2 = -3 < 0, move left pointer right

i=-4 ↑, left=-1 ->, right=2 ← (left moves to index 2)

Why: Sum too small, increase sum by moving left pointer

Step 4: Sum = -4 + (-1) + 2 = -3 < 0, move left pointer right

i=-4 ↑, left=-1 ->, right=2 ← (left moves to index 3)

Why: Sum still too small, move left pointer again

Step 5: Sum = -4 + 0 + 2 = -2 < 0, move left pointer right

i=-4 ↑, left=0 ->, right=2 ← (left moves to index 4)

Why: Sum still less than zero, move left pointer

Step 6: Sum = -4 + 1 + 2 = -1 < 0, move left pointer right

i=-4 ↑, left=1 ->, right=2 ← (left meets right, stop)

Why: No triplet found with i=0, move to next i

Step 7: Set i=1 (value -1), left=2, right=5

i=-1 ↑, left=-1 ->, right=2 ←

Why: Check triplets starting with -1

Step 8: Sum = -1 + (-1) + 2 = 0, record triplet [-1, -1, 2], move left and right skipping duplicates

Triplets: [-1, -1, 2]
left moves to 3, right moves to 4

Why: Found a valid triplet, move pointers to find others

Step 9: Sum = -1 + 0 + 1 = 0, record triplet [-1, 0, 1], move left and right skipping duplicates

Triplets: [-1, -1, 2], [-1, 0, 1]
left moves to 4, right moves to 3 (left >= right, stop)

Why: Found another valid triplet, no more with i=1

Step 10: Set i=2 (value -1), skip because same as previous i

Skip i=2 to avoid duplicate triplets

Why: Avoid duplicate triplets by skipping same values for i

Step 11: Set i=3 (value 0), left=4, right=5

i=0 ↑, left=1 ->, right=2 ←

Why: Check triplets starting with 0

Step 12: Sum = 0 + 1 + 2 = 3 > 0, move right pointer left

i=0 ↑, left=1 ->, right=1 ← (left >= right, stop)

Why: Sum too big, decrease sum by moving right pointer

Result:

Triplets found:
[-1, -1, 2]
[-1, 0, 1]

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

int cmpfunc(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

void threeSum(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), cmpfunc); // sort array
    for (int i = 0; i < numsSize - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates for i
        int left = i + 1;
        int right = numsSize - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                printf("[%d, %d, %d]\n", nums[i], nums[left], nums[right]);
                // skip duplicates for left
                while (left < right && nums[left] == nums[left + 1]) left++;
                // skip duplicates for right
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < 0) {
                left++; // increase sum
            } else {
                right--; // decrease sum
            }
        }
    }
}

int main() {
    int nums[] = {-1, 0, 1, 2, -1, -4};
    int size = sizeof(nums) / sizeof(nums[0]);
    threeSum(nums, size);
    return 0;
}

qsort(nums, numsSize, sizeof(int), cmpfunc); // sort array

sort array to enable two-pointer technique and duplicate skipping

if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates for i

skip duplicate values for i to avoid repeated triplets

while (left < right) { int sum = nums[i] + nums[left] + nums[right];

calculate sum of triplet candidates

if (sum == 0) { printf(...); while (left < right && nums[left] == nums[left + 1]) left++; while (left < right && nums[right] == nums[right - 1]) right--; left++; right--; }

found valid triplet, print and skip duplicates on both sides

else if (sum < 0) { left++; } else { right--; }

adjust pointers to increase or decrease sum

Output

[-1, -1, 2]

[-1, 0, 1]

Complexity Analysis

Time: O(n^2) because we sort once O(n log n) and then use two nested loops with two pointers scanning the array

Space: O(1) ignoring output space, as sorting is in-place and only pointers are used

vs Alternative: Naive approach is O(n^3) by checking all triplets; this method is faster due to sorting and two-pointer scanning

Edge Cases

empty array

no triplets found, function prints nothing

DSA C

for (int i = 0; i < numsSize - 2; i++) {

array with less than 3 elements

loop does not run, no output

DSA C

for (int i = 0; i < numsSize - 2; i++) {

array with all zeros

prints one triplet [0, 0, 0] once, skipping duplicates

DSA C

while (left < right && nums[left] == nums[left + 1]) left++;

When to Use This Pattern

When asked to find triplets summing to zero or a target with unique results, use sorting plus two-pointer scanning to efficiently find all unique triplets.

Common Mistakes

Mistake: Not sorting the array first, causing duplicate triplets and inefficient search
Fix: Sort the array before processing to enable two-pointer technique and duplicate skipping

Mistake: Not skipping duplicates for i, left, or right pointers, resulting in repeated triplets
Fix: Add checks to skip duplicate values for i, left, and right pointers after finding a valid triplet

Summary

Finds all unique triplets in an array that sum to zero.

Use when you need to find combinations of three numbers adding to zero without duplicates.

Sort the array and use two pointers to efficiently find triplets while skipping duplicates.