Three Sum Problem All Unique Triplets in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the goal of the Three Sum Problem?

To find all unique triplets in an array that add up to zero.

beginner

Why do we sort the array before solving the Three Sum Problem?

Sorting helps to avoid duplicates easily and allows using two pointers to find pairs efficiently.

intermediate

In the Two Pointer approach for Three Sum, what do the two pointers represent?

They represent the start and end of the subarray where we look for two numbers that sum to the negative of the current number.

intermediate

How do we avoid duplicate triplets in the Three Sum solution?

By skipping over duplicate numbers for the current index and also skipping duplicates when moving the two pointers.

intermediate

What is the time complexity of the optimized Three Sum solution using sorting and two pointers?

O(n^2), where n is the number of elements in the array.

What is the first step in solving the Three Sum Problem efficiently?

A Find the maximum element

B Use a hash map

C Reverse the array

D Sort the array

Sorting the array helps to use the two pointer technique and avoid duplicates.

In the Three Sum Problem, after fixing one element, what technique is commonly used to find the other two elements?

A Binary search

B Two pointers

C Brute force

D Recursion

Two pointers are used to find pairs that sum to the negative of the fixed element.

How do you handle duplicates when the fixed element is the same as the previous one?

A Skip it

B Include it anyway

C Double count it

D Reverse the array

Skipping duplicates prevents repeated triplets in the result.

What is the main reason for moving the left pointer forward when the sum is less than zero?

A To increase the sum

B To decrease the sum

C To find duplicates

D To reset pointers

Moving the left pointer forward increases the sum because the array is sorted.

What data structure is NOT typically used in the optimized Three Sum solution?

A Array

B HashSet

C Stack

D List

Stack is not used; the solution mainly uses arrays, lists, and sometimes hash sets to avoid duplicates.

Explain the step-by-step approach to solve the Three Sum Problem with unique triplets.

Think about sorting and two pointers working together.

Describe how to avoid duplicate triplets in the Three Sum Problem solution.

Duplicates appear when same numbers are repeated; skipping helps.

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