Three Sum Problem All Unique Triplets in DSA C# - Execution Trace

Concept Flow - Three Sum Problem All Unique Triplets

Sort the array

↓

For each element i

↓

Set left = i+1, right = end

↓

While left < right

↓

Sum == 0?

↓

Add triplet

↓

Skip duplicates

↓

Move left and right pointers

↓

Repeat until left >= right

↓

Repeat for next i

↓

Return all unique triplets

Sort the array, then for each element use two pointers to find pairs that sum to zero with it, skipping duplicates to get unique triplets.

Execution Sample

DSA C#

int[] nums = {-1, 0, 1, 2, -1, -4};
Array.Sort(nums);
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) {
      // add triplet
      // move left and right pointers skipping duplicates
      left++;
      right--;
    } else if (sum < 0) left++;
    else right--;
  }
}

This code sorts the array and uses a fixed element with two pointers to find all unique triplets summing to zero.

Execution Table

Step	Operation	i	left	right	Sum	Triplets Found	Pointer Changes	Visual State
1	Sort array	-	-	-	-	[]	-	[-4, -1, -1, 0, 1, 2]
2	Set i=0	0	1	5	-	[]	Set left=1, right=5	[-4, -1, -1, 0, 1, 2]
3	Calculate sum	0	1	5	-4 + (-1) + 2 = -3	[]	sum < 0, move left++	[-4, -1, -1, 0, 1, 2]
4	Move left	0	2	5	-	[]	left=2	[-4, -1, -1, 0, 1, 2]
5	Calculate sum	0	2	5	-4 + (-1) + 2 = -3	[]	sum < 0, move left++	[-4, -1, -1, 0, 1, 2]
6	Move left	0	3	5	-	[]	left=3	[-4, -1, -1, 0, 1, 2]
7	Calculate sum	0	3	5	-4 + 0 + 2 = -2	[]	sum < 0, move left++	[-4, -1, -1, 0, 1, 2]
8	Move left	0	4	5	-	[]	left=4	[-4, -1, -1, 0, 1, 2]
9	Calculate sum	0	4	5	-4 + 1 + 2 = -1	[]	sum < 0, move left++	[-4, -1, -1, 0, 1, 2]
10	Move left	0	5	5	-	[]	left=5	[-4, -1, -1, 0, 1, 2]
11	left >= right, move i	1	2	5	-	[]	Set left=2, right=5	[-4, -1, -1, 0, 1, 2]
12	Calculate sum	1	2	5	-1 + (-1) + 2 = 0	[[-1, -1, 2]]	sum == 0, add triplet, move left++ and right--	[-4, -1, -1, 0, 1, 2]
13	After pointer move	1	3	4	-	[[-1, -1, 2]]	left=3, right=4	[-4, -1, -1, 0, 1, 2]
14	Calculate sum	1	3	4	-1 + 0 + 1 = 0	[[-1, -1, 2], [-1, 0, 1]]	sum == 0, add triplet, move left++ and right--	[-4, -1, -1, 0, 1, 2]
15	Move pointers	1	4	3	-	[[-1, -1, 2], [-1, 0, 1]]	left=4, right=3	[-4, -1, -1, 0, 1, 2]
16	left >= right, move i	2	3	5	-	[[-1, -1, 2], [-1, 0, 1]]	Set left=3, right=5	[-4, -1, -1, 0, 1, 2]
17	Skip duplicate i=2 (nums[2] == nums[1])	2	-	-	-	[[-1, -1, 2], [-1, 0, 1]]	Skip i=2 to avoid duplicates	[-4, -1, -1, 0, 1, 2]
18	Move i=3	3	4	5	-	[[-1, -1, 2], [-1, 0, 1]]	Set left=4, right=5	[-4, -1, -1, 0, 1, 2]
19	Calculate sum	3	4	5	0 + 1 + 2 = 3	[[-1, -1, 2], [-1, 0, 1]]	sum > 0, move right--	[-4, -1, -1, 0, 1, 2]
20	Move right	3	4	4	-	[[-1, -1, 2], [-1, 0, 1]]	right=4	[-4, -1, -1, 0, 1, 2]
21	left >= right, end loop	-	-	-	-	[[-1, -1, 2], [-1, 0, 1]]	left >= right, stop	[-4, -1, -1, 0, 1, 2]

💡 All elements processed or pointers crossed, all unique triplets found.

Variable Tracker

Variable	Start	After Step 2	After Step 11	After Step 16	Final
i	-	0	1	2	3
left	-	1	2	3	4
right	-	5	5	5	4
Triplets Found	[]	[]	[]	[[-1, -1, 2], [-1, 0, 1]]	[[-1, -1, 2], [-1, 0, 1]]

Key Moments - 3 Insights

Why do we skip duplicate values for i and left pointers?

Skipping duplicates prevents adding the same triplet multiple times. For example, at step 17, i=2 is skipped because nums[2] equals nums[1], avoiding repeated triplets as shown in execution_table rows 12-14.

Why do we move left pointer when sum < 0 and right pointer when sum > 0?

Because the array is sorted, if sum < 0, increasing left moves to a bigger number to increase sum (steps 3-9). If sum > 0, decreasing right moves to a smaller number to reduce sum (step 19).

Why does the loop stop when left >= right?

When left meets or passes right, all pairs for current i are checked. Continuing would repeat or cross pairs, so the loop ends (steps 15, 20-21).

Visual Quiz - 3 Questions

Look at the execution_table at step 12, what triplet is added?

A [-1, -1, 2]

B [-1, 0, 1]

C [0, 1, 2]

D [-4, 1, 3]

💡 Hint

Check the 'Triplets Found' column at step 12 in execution_table.

At which step does the left pointer first move from 1 to 2?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Pointer Changes' and 'left' column between steps 3 and 5.

If the array was not sorted, how would the pointer movement logic change?

A Pointers would still move left++ or right-- based on sum comparison.

B Pointer movement would be unpredictable; sorting is needed for two-pointer logic.

C We would only move the right pointer regardless of sum.

D We would not use pointers at all.

💡 Hint

Refer to the concept_flow where sorting is the first step before pointer usage.

Concept Snapshot

Three Sum Problem:
- Sort the array first.
- Fix one element i.
- Use two pointers (left=i+1, right=end).
- Move pointers based on sum:
  sum == 0: add triplet, move both pointers skipping duplicates.
  sum < 0: move left++ to increase sum.
  sum > 0: move right-- to decrease sum.
- Repeat for all i, skip duplicates.
- Return all unique triplets.

Full Transcript

The Three Sum problem finds all unique triplets in an array that sum to zero. We start by sorting the array to use a two-pointer approach efficiently. For each element i, we set two pointers: left just after i, and right at the end. We calculate the sum of nums[i], nums[left], and nums[right]. If the sum is zero, we add the triplet and move both pointers, skipping duplicates to avoid repeated triplets. If the sum is less than zero, we move left pointer forward to increase the sum. If the sum is greater than zero, we move right pointer backward to decrease the sum. We repeat this until left meets or passes right, then move to the next i, skipping duplicates. This process continues until all elements are processed. The final result is a list of all unique triplets that sum to zero.

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