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

↓

Repeat until all i processed

↓

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.

Execution Sample

DSA C

int threeSum(int* nums, int numsSize) {
  // Sort nums
  // For i in 0 to numsSize-3
  //   left = i+1, right = numsSize-1
  //   while left < right
  //     sum = nums[i]+nums[left]+nums[right]
  //     if sum == 0 add triplet and skip duplicates
  //     else move pointers
}

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

Execution Table

Step	Operation	i	left	right	Sum	Triplets Found	Pointer Changes	Array State
1	Sort array	-	-	-	-	[]	-	[-4, -1, -1, 0, 1, 2]
2	Set i=0	0	-	-	-	[]	-	[-4, -1, -1, 0, 1, 2]
3	Set left=1, right=5	0	1	5	-	[]	-	[-4, -1, -1, 0, 1, 2]
4	Calculate sum	0	1	5	-4 + (-1) + 2 = -3	[]	-	[-4, -1, -1, 0, 1, 2]
5	Sum < 0, move left	0	2	5	-	[]	left++	[-4, -1, -1, 0, 1, 2]
6	Calculate sum	0	2	5	-4 + (-1) + 2 = -3	[]	-	[-4, -1, -1, 0, 1, 2]
7	Sum < 0, move left	0	3	5	-	[]	left++	[-4, -1, -1, 0, 1, 2]
8	Calculate sum	0	3	5	-4 + 0 + 2 = -2	[]	-	[-4, -1, -1, 0, 1, 2]
9	Sum < 0, move left	0	4	5	-	[]	left++	[-4, -1, -1, 0, 1, 2]
10	Calculate sum	0	4	5	-4 + 1 + 2 = -1	[]	-	[-4, -1, -1, 0, 1, 2]
11	Sum < 0, move left	0	5	5	-	[]	left++	[-4, -1, -1, 0, 1, 2]
12	left >= right, move i	1	-	-	-	[]	-	[-4, -1, -1, 0, 1, 2]
13	Set left=2, right=5	1	2	5	-	[]	-	[-4, -1, -1, 0, 1, 2]
14	Calculate sum	1	2	5	-1 + (-1) + 2 = 0	[]	-	[-4, -1, -1, 0, 1, 2]
15	Sum == 0, add triplet	1	2	5	0	[[-1,-1,2]]	-	[-4, -1, -1, 0, 1, 2]
16	Skip duplicates left	1	3	5	-	[[-1,-1,2]]	left++	[-4, -1, -1, 0, 1, 2]
17	Skip duplicates right	1	3	4	-	[[-1,-1,2]]	right--	[-4, -1, -1, 0, 1, 2]
18	Calculate sum	1	3	4	-1 + 0 + 1 = 0	[[-1,-1,2]]	-	[-4, -1, -1, 0, 1, 2]
19	Sum == 0, add triplet	1	3	4	0	[[-1,-1,2],[-1,0,1]]	-	[-4, -1, -1, 0, 1, 2]
20	Skip duplicates left	1	4	4	-	[[-1,-1,2],[-1,0,1]]	left++	[-4, -1, -1, 0, 1, 2]
21	left >= right, move i	2	-	-	-	[[-1,-1,2],[-1,0,1]]	-	[-4, -1, -1, 0, 1, 2]
22	i=2 is duplicate of i=1, skip i	3	-	-	-	[[-1,-1,2],[-1,0,1]]	-	[-4, -1, -1, 0, 1, 2]
23	Set left=4, right=5	3	4	5	-	[[-1,-1,2],[-1,0,1]]	-	[-4, -1, -1, 0, 1, 2]
24	Calculate sum	3	4	5	0 + 1 + 2 = 3	[[-1,-1,2],[-1,0,1]]	-	[-4, -1, -1, 0, 1, 2]
25	Sum > 0, move right	3	4	4	-	[[-1,-1,2],[-1,0,1]]	right--	[-4, -1, -1, 0, 1, 2]
26	left >= right, move i	4	-	-	-	[[-1,-1,2],[-1,0,1]]	-	[-4, -1, -1, 0, 1, 2]
27	i=4, no enough elements for triplet, end	-	-	-	-	[[-1,-1,2],[-1,0,1]]	-	[-4, -1, -1, 0, 1, 2]

💡 i reached end where no triplets possible, all unique triplets found

Variable Tracker

Variable	Start	After Step 2	After Step 15	After Step 23	Final
i	-	0	1	3	4
left	-	-	2	4	-
right	-	-	5	5	-
Triplets Found	[]	[]	[[-1,-1,2]]	[[-1,-1,2],[-1,0,1]]	[[-1,-1,2],[-1,0,1]]
Array State	[-4,-1,-1,0,1,2]	[-4,-1,-1,0,1,2]	[-4,-1,-1,0,1,2]	[-4,-1,-1,0,1,2]	[-4,-1,-1,0,1,2]

Key Moments - 3 Insights

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

Skipping duplicates avoids repeated triplets. See steps 22 and 16 where duplicates are skipped to keep triplets unique.

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

Because the array is sorted, moving left pointer increases sum, moving right pointer decreases sum. See steps 4-11 and 24-25.

Why stop when left >= right?

Because left and right pointers cross means all pairs for current i are checked. See step 11 and 20.

Visual Quiz - 3 Questions

Look at the execution table at step 15, what triplet is added?

A [-1, -1, 2]

B [-4, 0, 4]

C [0, 1, -1]

D [-1, 0, 1]

💡 Hint

Check the 'Triplets Found' column at step 15 in the execution table.

At which step does the left pointer move after finding the first triplet?

A Step 16

B Step 14

C Step 18

D Step 20

💡 Hint

Look at the 'Pointer Changes' column after step 15 in the execution table.

If the array was not sorted, which part of the execution would fail?

A Skipping duplicates

B Moving pointers based on sum comparison

C Adding triplets

D Setting initial pointers

💡 Hint

Refer to steps 4-11 and 24-25 where pointer moves depend on sum comparison assuming sorted array.

Concept Snapshot

Three Sum Problem:
- Sort array first
- For each element i, use two pointers left=i+1 and right=end
- Calculate sum = nums[i]+nums[left]+nums[right]
- If sum == 0, add triplet and skip duplicates
- If sum < 0, move left pointer right
- If sum > 0, move right pointer left
- Repeat until all i processed
- Return all unique triplets

Full Transcript

The Three Sum Problem finds all unique triplets in an array that sum to zero. First, the array is sorted to allow two-pointer technique. For each element i, two pointers left and right are set to the next element and the end of the array. The sum of nums[i], nums[left], and nums[right] is calculated. If the sum is zero, the triplet is added to the result and pointers skip duplicates. If the sum is less than zero, the left pointer moves right to increase sum. If the sum is greater than zero, the right pointer moves left to decrease sum. This continues until left meets right. Then i moves forward, skipping duplicates. The process repeats until all elements are processed. The final result contains all unique triplets that sum to zero.

Practice

1. What is the main goal of the Three Sum Problem in data structures and algorithms?

easy

A. Find the maximum sum of any three elements

B. Sort the array in ascending order

C. Count the number of pairs that sum to zero

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

Solution

1. Step 1: Understand the problem statement

   The Three Sum Problem asks to find all unique sets of three numbers in an array whose sum is zero.

2. Step 2: Differentiate from other options

   Options A, B, and D describe different problems like maximum sum, sorting, or pairs, not triplets summing to zero.

3. Final Answer:

   Find all unique triplets in an array that sum to zero -> Option D

4. Quick Check:

   Three Sum Problem = Find triplets summing to zero [OK]

Hint: Remember: Three Sum finds triplets with zero sum [OK]

Common Mistakes:

• Confusing with pair sum problems
• Thinking it finds maximum sums
• Assuming it sorts the array only

2. Which of the following code snippets correctly initializes the array for solving the Three Sum Problem in C?

easy

A. int nums[] = { -1, 0, 1, 2, -1, -4 }; int size = sizeof(nums) / sizeof(nums[0]);

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

C. int nums[] = (-1, 0, 1, 2, -1, -4); int size = 6;

D. int nums[] = [-1, 0, 1, 2, -1, -4]; int size = 6;

Solution

1. Step 1: Check array initialization syntax in C

   In C, arrays are initialized with curly braces {}, not parentheses or square brackets.

2. Step 2: Verify size calculation

   int nums[] = { -1, 0, 1, 2, -1, -4 }; int size = sizeof(nums) / sizeof(nums[0]); correctly calculates size using sizeof operator divided by element size.

3. Final Answer:

   int nums[] = { -1, 0, 1, 2, -1, -4 }; int size = sizeof(nums) / sizeof(nums[0]); -> Option A

4. Quick Check:

   C array init with {} and sizeof = int nums[] = { -1, 0, 1, 2, -1, -4 }; int size = sizeof(nums) / sizeof(nums[0]); [OK]

Hint: Use curly braces {} for arrays in C [OK]

Common Mistakes:

• Using parentheses () instead of braces {}
• Using square brackets [] for initialization
• Not calculating size correctly

3. What will be the output of the following C code snippet that attempts to find unique triplets summing to zero?

int nums[] = {-1, 0, 1, 2, -1, -4};
int size = 6;
// Assume function threeSum prints triplets
threeSum(nums, size);
// Output format: each triplet printed as (a, b, c)

medium

A. No triplets found

B. (-4, 2, 2)
(-1, 0, 1)

C. (-1, -1, 2)
(-1, 0, 1)

D. (0, 0, 0)
(-1, 1, 2)

Solution

1. Step 1: Identify triplets that sum to zero

   From the array {-1, 0, 1, 2, -1, -4}, the unique triplets summing to zero are (-1, -1, 2) and (-1, 0, 1).

2. Step 2: Verify output matches these triplets

   (-1, -1, 2) (-1, 0, 1) lists these exact triplets; other options include invalid or non-existent triplets.

3. Final Answer:

   (-1, -1, 2) (-1, 0, 1) -> Option C

4. Quick Check:

   Unique triplets summing zero = (-1, -1, 2) (-1, 0, 1) [OK]

Hint: Check sums of triplets carefully for zero [OK]

Common Mistakes:

• Including duplicates like (-4, 2, 2)
• Assuming zero triplets when some exist
• Mixing up triplet elements

4. Identify the bug in the following C code snippet for the Three Sum Problem:

void threeSum(int* nums, int size) {
    for (int i = 0; i < size - 2; i++) {
        for (int j = i + 1; j < size - 1; j++) {
            for (int k = j + 1; k < size; k++) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    printf("(%d, %d, %d)\n", nums[i], nums[j], nums[k]);
                }
            }
        }
    }
}

medium

A. Does not avoid printing duplicate triplets

B. Loops have incorrect ranges causing out-of-bounds access

C. Sum condition should be nums[i] * nums[j] * nums[k] == 0

D. Missing return statement in void function

Solution

1. Step 1: Analyze triplet printing logic

   The code prints any triplet summing to zero but does not check for duplicates, so duplicate triplets may print multiple times.

2. Step 2: Check loop ranges and conditions

   Loop ranges are correct and sum condition is correct; void functions do not require return statements.

3. Final Answer:

   Does not avoid printing duplicate triplets -> Option A

4. Quick Check:

   Duplicate triplets not filtered = Does not avoid printing duplicate triplets [OK]

Hint: Check if duplicates are filtered in nested loops [OK]

Common Mistakes:

• Confusing sum with product condition
• Thinking void needs return
• Assuming loops cause out-of-bounds

5. Given the array int nums[] = {0, 0, 0, 0}; and size 4, what is the correct output of a Three Sum solution that finds all unique triplets summing to zero?

hard

A. No triplets found

B. (0, 0, 0)

C. (0, 0, 0)
(0, 0, 0)

D. (0, 0, 0)
(0, 0, 0)
(0, 0, 0)

Solution

1. Step 1: Identify unique triplets summing to zero

   All elements are zero, so the only unique triplet is (0, 0, 0).

2. Step 2: Avoid duplicates in output

   Even though multiple combinations exist, only one unique triplet should be printed.

3. Final Answer:

   (0, 0, 0) -> Option B

4. Quick Check:

   Unique triplet from zeros = (0, 0, 0) [OK]

Hint: Only print unique triplets, even if duplicates exist [OK]

Common Mistakes:

• Printing duplicate triplets multiple times
• Assuming no triplets because all zeros
• Confusing triplet uniqueness