Three Sum Problem All Unique Triplets in DSA C#

Mental Model

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

Analogy: Imagine you have a group of friends with different money amounts, and you want to find three friends whose total money sums to zero, but you don't want to count the same group twice.

nums: [-4] -> [-1] -> [-1] -> [0] -> [1] -> [2] -> null
indexes: 0    1     2     3    4    5

Dry Run Walkthrough

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

Goal: Find all unique triplets that sum to zero

Step 1: Sort the list to [-4, -1, -1, 0, 1, 2]

[-4] -> [-1] -> [-1] -> [0] -> [1] -> [2] -> null

Why: Sorting helps to use two pointers and avoid duplicates easily

Step 2: Set first pointer i=0 at -4, set left=1, right=5

i->[-4], left->[-1], right->[2]

Why: Start checking pairs with -4 to find sum zero triplets

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

i->[-4], left->[-1 (index 2)], right->[2]

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

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

i->[-4], left->[0], right->[2]

Why: Sum still too small, move left pointer right again

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

i->[-4], left->[1], right->[2]

Why: Sum still less than zero, move left pointer right

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

i->[-4], left->[2], right->[2]

Why: Left and right pointers meet, no triplet with i=0

Step 7: Increment i to 1 at -1, set left=2, right=5

i->[-1], left->[-1], right->[2]

Why: Try next number as first element of triplet

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

triplets: [[-1, -1, 2]]
i->[-1], left->[0], right->[1]

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

Step 9: Calculate sum = -1 + 0 + 1 = 0, record triplet [-1, 0, 1], move left and right pointers

triplets: [[-1, -1, 2], [-1, 0, 1]]
i->[-1], left->[1], right->[0]

Why: Found another valid triplet

Step 10: Left pointer meets right pointer, increment i to 2 at -1 (skip duplicate), then i=3 at 0

i->[0], left->[1], right->[2]

Why: Skip duplicate i and continue searching

Step 11: Calculate sum = 0 + 1 + 2 = 3 > 0, move right pointer left

i->[0], left->[1], right->[1]

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

Step 12: Left and right pointers meet, end search

triplets: [[-1, -1, 2], [-1, 0, 1]]

Why: No more triplets possible

Result:

[-1] -> [-1] -> [2] -> null
[-1] -> [0] -> [1] -> null
All unique triplets that sum to zero

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class ThreeSum {
    public static IList<IList<int>> FindTriplets(int[] nums) {
        Array.Sort(nums); // sort array to use two pointers
        IList<IList<int>> result = new List<IList<int>>();
        for (int i = 0; i < nums.Length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates for i
            int left = i + 1;
            int right = nums.Length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    result.Add(new List<int>{nums[i], nums[left], nums[right]});
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++; // skip duplicates
                    while (left < right && nums[right] == nums[right + 1]) right--; // skip duplicates
                } else if (sum < 0) {
                    left++; // increase sum
                } else {
                    right--; // decrease sum
                }
            }
        }
        return result;
    }

    static void Main() {
        int[] nums = new int[] {-1, 0, 1, 2, -1, -4};
        var triplets = FindTriplets(nums);
        foreach (var triplet in triplets) {
            Console.WriteLine(string.Join(" -> ", triplet) + " -> null");
        }
    }
}

Array.Sort(nums); // sort array to use two pointers

sort input to enable two-pointer technique and duplicate skipping

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

skip duplicate first elements to avoid repeated triplets

while (left < right) {

iterate with two pointers to find pairs that sum with nums[i] to zero

if (sum == 0) { result.Add(...); left++; right--; ... }

found a triplet, add to result and move pointers skipping duplicates

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

adjust pointers to increase or decrease sum towards zero

Output

-1 -> -1 -> 2 -> null

-1 -> 0 -> 1 -> null

Complexity Analysis

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

Space: O(k) where k is number of triplets found, for storing results

vs Alternative: Naive approach is O(n^3) by checking all triplets; this two-pointer method is much faster

Edge Cases

empty array

returns empty list, no triplets found

DSA C#

for (int i = 0; i < nums.Length - 2; i++)

array with less than 3 elements

returns empty list, no triplets possible

DSA C#

for (int i = 0; i < nums.Length - 2; i++)

array with all zeros

returns one triplet [0,0,0] only once

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 no duplicates, use sorting plus two pointers to efficiently find unique triplets.

Common Mistakes

Mistake: Not sorting the array before applying two pointers
Fix: Sort the array first to enable two-pointer technique and duplicate skipping

Mistake: Not skipping duplicates for i, left, or right pointers
Fix: Add checks to skip duplicate values to avoid repeated triplets

Mistake: Moving pointers incorrectly when sum equals zero
Fix: After finding a triplet, move both pointers and skip duplicates before continuing

Summary

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

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

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

Practice

1. What is the main goal of the Three Sum Problem All Unique Triplets in an integer array?

easy

A. Find all unique triplets that sum to zero

B. Find the maximum sum of any three numbers

C. Sort the array in ascending order

D. Count the number of pairs that sum to zero

Solution

1. Step 1: Understand the problem statement

   The problem asks to find all unique groups of three numbers (triplets) in the array whose sum equals zero.

2. Step 2: Clarify the output requirement

   We must return all such triplets without duplicates, not just count or sort.

3. Final Answer:

   Find all unique triplets that sum to zero -> Option A

4. Quick Check:

   Goal = unique triplets summing to zero [OK]

Hint: Look for three numbers adding to zero without duplicates [OK]

Common Mistakes:

• Confusing triplets with pairs
• Trying to find max sum instead of zero sum
• Ignoring uniqueness of triplets

2. Which of the following C# code snippets correctly initializes an integer array named nums for the Three Sum problem?

easy

A. int[] nums = (-1, 0, 1, 2, -1, -4);

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

C. int[] nums = new int[] { -1, 0, 1, 2, -1, -4 };

D. int[] nums = new List<int> { -1, 0, 1, 2, -1, -4 };

Solution

1. Step 1: Check array initialization syntax in C#

   Correct syntax for array initialization is: int[] nums = new int[] { ... };

2. Step 2: Validate each option

   int[] nums = new int[] { -1, 0, 1, 2, -1, -4 }; uses correct syntax. int nums = { -1, 0, 1, 2, -1, -4 }; misses array type. int[] nums = (-1, 0, 1, 2, -1, -4); uses parentheses instead of braces. int[] nums = new List<int> { -1, 0, 1, 2, -1, -4 }; tries to assign a List to an array variable.

3. Final Answer:

   int[] nums = new int[] { -1, 0, 1, 2, -1, -4 }; -> Option C

4. Quick Check:

   Array init syntax = int[] nums = new int[] { -1, 0, 1, 2, -1, -4 }; [OK]

Hint: Use new int[] { ... } to initialize arrays in C# [OK]

Common Mistakes:

• Using parentheses instead of braces
• Assigning List to array variable
• Missing type declaration

3. What is the output of the following C# code snippet that finds all unique triplets summing to zero?

int[] nums = { -1, 0, 1, 2, -1, -4 };
var result = ThreeSum(nums);
foreach(var triplet in result) {
    Console.WriteLine(string.Join(", ", triplet));
}

// Assume ThreeSum returns List of unique triplets

medium

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

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

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

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

Solution

1. Step 1: Sort and find triplets summing to zero

   Sorted array: [-4, -1, -1, 0, 1, 2]. Triplets summing to zero are [-1, -1, 2] and [-1, 0, 1].

2. Step 2: Match output with options

   [-1, 0, 1] [-1, -1, 2] lists these two triplets correctly. Others contain invalid or impossible triplets.

3. Final Answer:

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

4. Quick Check:

   Unique triplets = [-1, 0, 1] [-1, -1, 2] [OK]

Hint: Sort array first, then find triplets with two-pointer [OK]

Common Mistakes:

• Not sorting before searching
• Including duplicate triplets
• Wrong triplet sums

4. Identify the bug in this C# code snippet for the Three Sum problem:

public IList ThreeSum(int[] nums) {
    var result = new List();
    Array.Sort(nums);
    for (int i = 0; i < nums.Length - 2; i++) {
        int left = i + 1, right = nums.Length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.Add(new List<int> { nums[i], nums[left], nums[right] });
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

medium

A. No check to skip duplicate values for i, left, and right

B. Array is not sorted before processing

C. Incorrect sum calculation formula

D. Using List instead of Array for result

Solution

1. Step 1: Analyze duplicate handling in loops

   The code does not skip duplicate values for i, left, or right, which can cause duplicate triplets in the result.

2. Step 2: Verify other parts

   Array is sorted, sum calculation is correct, and List usage is valid. So only duplicate skipping is missing.

3. Final Answer:

   No check to skip duplicate values for i, left, and right -> Option A

4. Quick Check:

   Missing duplicate skip = No check to skip duplicate values for i, left, and right [OK]

Hint: Always skip duplicates after finding a valid triplet [OK]

Common Mistakes:

• Not skipping duplicates causing repeated triplets
• Forgetting to sort array
• Wrong sum calculation

5. Given the input array nums = [-2, 0, 1, 2, -1, -1, 2], which of the following lists contains all unique triplets that sum to zero?

hard

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

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

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

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

Solution

1. Step 1: Sort the array and find triplets

   Sorted nums: [-2, -1, -1, 0, 1, 2, 2]. Valid unique triplets summing to zero are [-2, 0, 2], [-1, -1, 2], and [-1, 0, 1].

2. Step 2: Compare with options

   [[-2, 0, 2], [-1, -1, 2], [-1, 0, 1]] matches these triplets exactly. Others contain invalid or duplicate triplets.

3. Final Answer:

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

4. Quick Check:

   All unique triplets = [[-2, 0, 2], [-1, -1, 2], [-1, 0, 1]] [OK]

Hint: Sort array, then use two pointers to find triplets [OK]

Common Mistakes:

• Including triplets with wrong sums
• Missing duplicates in output
• Ignoring sorting step