Three Sum Problem All Unique Triplets in DSA C# - Deep Dive

Overview - Three Sum Problem All Unique Triplets

What is it?

The Three Sum Problem asks us to find all unique groups of three numbers in a list that add up to zero. Each group is called a triplet. We want to list all such triplets without repeating any. This problem helps us understand how to efficiently search combinations in arrays.

Why it matters

Without a method like this, finding all triplets that sum to zero would take too long, especially for big lists. This problem teaches us how to reduce time by sorting and using two pointers. It is important because similar patterns appear in real-world tasks like finding matching sets or balancing values.

Where it fits

Before this, you should know arrays, sorting, and the two-pointer technique. After this, you can learn more complex combination problems and optimization techniques like hashing or backtracking.

Mental Model

Core Idea

Sort the list and use two pointers to find pairs that, with a fixed number, sum to zero without duplicates.

Think of it like...

Imagine you have a sorted row of people with different heights. You pick one person and then look for two others whose heights together balance out to a perfect middle height. You move inward from both ends to find these pairs quickly.

Sorted array: [-4, -1, -1, 0, 1, 2]
Fix one number (index i) -> Use two pointers (left, right) to find pairs:

 i
 ↓
[-4, -1, -1, 0, 1, 2]
      ↑           ↑
    left        right

Move left and right pointers inward to find sums equal to -nums[i].

Build-Up - 6 Steps

1

Foundation

Understanding the Problem Setup

Concept: Learn what the problem asks: find all unique triplets that sum to zero.

Given an array of integers, we want to find all groups of three numbers where their sum is zero. For example, in [-1, 0, 1, 2, -1, -4], the triplets are [-1, -1, 2] and [-1, 0, 1]. We must avoid duplicates.

Result

Clear understanding of the problem and expected output format.

Knowing exactly what the problem asks prevents confusion and guides the choice of approach.

2

Foundation

Sorting the Array First

Concept: Sort the array to make searching easier and to handle duplicates.

Sorting the input array arranges numbers in order, e.g. [-4, -1, -1, 0, 1, 2]. This helps us use two pointers and skip duplicates efficiently.

Result

Sorted array ready for efficient searching.

Sorting transforms a complex search into a structured one, enabling faster and simpler logic.

3

Intermediate

Fix One Number and Use Two Pointers

🤔Before reading on: do you think fixing one number and searching pairs with two pointers is faster than checking all triplets? Commit to yes or no.

Concept: Fix one number and find two others using two pointers to sum to zero.

For each number at index i, set two pointers: left = i+1 and right = end of array. Move pointers inward based on sum compared to target (-nums[i]). If sum is too small, move left up; if too big, move right down.

Result

Pairs found efficiently for each fixed number.

Using two pointers after sorting reduces complexity from cubic to quadratic, making the problem solvable for larger inputs.

4

Intermediate

Skipping Duplicates to Ensure Unique Triplets

🤔Before reading on: do you think skipping duplicates is necessary to avoid repeated triplets? Commit to yes or no.

Concept: Skip repeated numbers at each step to avoid duplicate triplets in the result.

After sorting, if the current number is the same as the previous, skip it. Similarly, after finding a valid triplet, move pointers past duplicates to avoid repeating the same triplet.

Result

Only unique triplets are collected.

Skipping duplicates prevents redundant work and ensures the output meets the problem's uniqueness requirement.

5

Advanced

Implementing Complete Three Sum Solution in C#

🤔Before reading on: do you think the two-pointer approach can be implemented in under 30 lines of code? Commit to yes or no.

Concept: Combine sorting, fixing, two pointers, and duplicate skipping into a full working solution.

```csharp using System; using System.Collections.Generic; public class Solution { public IList> ThreeSum(int[] nums) { Array.Sort(nums); var result = new List>(); for (int i = 0; i < nums.Length - 2; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates 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{nums[i], 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 < 0) { left++; } else { right--; } } } return result; } } ```

Result

All unique triplets that sum to zero are found and returned.

Combining all techniques into code shows how theory translates into practical, efficient solutions.

6

Expert

Optimizing and Understanding Edge Cases

🤔Before reading on: do you think the algorithm handles empty arrays and arrays with fewer than three elements correctly? Commit to yes or no.

Concept: Handle edge cases and understand performance limits of the solution.

The solution returns empty if input has fewer than three numbers. It handles arrays with all positive or all negative numbers by skipping unnecessary searches. Time complexity is O(n^2), which is optimal for this problem. Memory usage is minimal, only storing results.

Result

Robust solution that works correctly on all valid inputs and performs efficiently.

Knowing edge cases and performance boundaries ensures the solution is reliable and practical in real-world use.

Under the Hood

The algorithm sorts the array to enable the two-pointer technique. Fixing one number, it searches pairs that sum to the negative of that number by moving two pointers inward based on the sum comparison. Skipping duplicates avoids repeated triplets. Internally, sorting takes O(n log n), and the two-pointer search takes O(n) for each fixed number, resulting in O(n^2) overall.

Why designed this way?

Sorting and two pointers were chosen to reduce the brute force O(n^3) approach to O(n^2). Alternatives like hashing can use extra space and may be less efficient. The design balances speed and memory use, making it practical for large inputs.

Input array
  ↓
Sorted array
  ↓
For each index i:
  ├─ Fix nums[i]
  ├─ Set left = i+1, right = end
  ├─ While left < right:
  │    ├─ sum = nums[i] + nums[left] + nums[right]
  │    ├─ If sum == 0 -> record triplet, move pointers skipping duplicates
  │    ├─ Else if sum < 0 -> left++
  │    └─ Else -> right--
  └─ Repeat for next i
Output: List of unique triplets

Myth Busters - 3 Common Misconceptions

Quick: Do you think sorting is optional for solving the Three Sum problem efficiently? Commit to yes or no.

Common Belief: Some believe you can find all triplets efficiently without sorting the array.

Reality: Sorting is essential to use the two-pointer technique and to skip duplicates efficiently. Without sorting, the problem becomes much harder and slower.

Why it matters: Skipping sorting leads to inefficient solutions that may time out or produce duplicate triplets.

Quick: Do you think checking all triplets with three nested loops is fast enough for large inputs? Commit to yes or no.

Common Belief: Many think brute force with three loops is acceptable for all input sizes.

Reality: Brute force is O(n^3), which is too slow for large arrays. The two-pointer method reduces it to O(n^2), making it practical.

Why it matters: Using brute force causes slow programs and poor user experience on big data.

Quick: Do you think duplicate triplets can be avoided by just checking the final result list? Commit to yes or no.

Common Belief: Some believe filtering duplicates after collecting all triplets is enough.

Reality: Filtering duplicates after the fact is inefficient. Skipping duplicates during the search is faster and cleaner.

Why it matters: Post-filtering wastes time and memory, making the solution less efficient.

Expert Zone

1

The order of skipping duplicates matters: skipping duplicates for the fixed number before the two-pointer loop and for left/right pointers inside the loop prevents subtle bugs.

2

When the fixed number is positive, you can stop early because all further numbers will be positive and sums cannot be zero.

3

Using a List of Lists for results is flexible but can be optimized with arrays or custom structs in performance-critical systems.

When NOT to use

This approach is not suitable if the problem requires counting triplets with multiplicities or if the target sum is not zero. For those, hashing or other algorithms like meet-in-the-middle may be better.

Production Patterns

In production, this pattern is used in financial systems to find balanced portfolios, in gaming to find balanced teams, and in recommendation engines to find complementary item sets. It is often combined with caching and early stopping for performance.

Connections

Two Pointer Technique

Builds-on

Understanding the two-pointer technique is key to solving the Three Sum problem efficiently, as it reduces the search space drastically.

Sorting Algorithms

Prerequisite

Sorting is a foundational step that enables efficient searching and duplicate handling in this problem.

Chemical Reaction Balancing

Analogous pattern

Balancing chemical equations involves finding sets of coefficients that sum to zero net change, similar to finding triplets summing to zero, showing how math patterns appear across fields.

Common Pitfalls

#1 Not skipping duplicates leads to repeated triplets in the output.

Wrong approach:

if (i > 0 && nums[i] == nums[i - 1]) { /* missing continue here */ }
// No skipping duplicates for left and right pointers

Correct approach:

if (i > 0 && nums[i] == nums[i - 1]) continue;
// After finding triplet:
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;

Root cause:

Misunderstanding that duplicates must be skipped during iteration, not just filtered later.

#2 Using three nested loops causes slow performance on large inputs.

Wrong approach:

for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
for (int k = j+1; k < n; k++)
if (nums[i] + nums[j] + nums[k] == 0) add triplet;

Correct approach:

Sort array;
for i in array:
use two pointers left and right to find pairs summing to -nums[i];

Root cause:

Not knowing the two-pointer technique and its efficiency benefits.

#3 Not handling edge cases like empty or small arrays causes errors.

Wrong approach:

Assuming input length >= 3 without checks, leading to index errors.

Correct approach:

if (nums.Length < 3) return empty list;

Root cause:

Overlooking input validation and boundary conditions.

Key Takeaways

Sorting the array is the first crucial step to enable efficient searching and duplicate handling.

Fixing one number and using two pointers to find pairs reduces the problem from cubic to quadratic time.

Skipping duplicates during iteration is essential to avoid repeated triplets and improve performance.

Handling edge cases and early stopping conditions makes the solution robust and practical.

The Three Sum problem teaches a pattern useful in many real-world scenarios involving combination searches.

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