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 = arr[i

↓

Repeat until all i processed

↓

Return all unique triplets

The array is sorted first. Then for each element, two pointers scan the rest to find triplets summing to zero, skipping duplicates.

Execution Sample

DSA C++

std::vector<int> nums = {-1, 0, 1, 2, -1, -4};
std::sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); i++) {
  if(i > 0 && nums[i] == nums[i-1]) continue; // skip duplicates
  int left = i+1, right = nums.size()-1;
  while(left < right) {
    int sum = nums[i]+nums[left]+nums[right];
    if(sum == 0) {
      // record triplet
      // move left and right skipping duplicates
    } else if(sum < 0) {
      left++;
    } else {
      right--;
    }
  }
}

This code sorts the array and uses two pointers to find triplets that sum to zero.

Execution Table

Step	Operation	i	left	right	Sum	Triplets Found	Pointer Moves	Array State
1	Sort array	-	-	-	-	[]	-	[-4, -1, -1, 0, 1, 2]
2	Set i=0	0	1	5	-	[]	-	[-4, -1, -1, 0, 1, 2]
3	Calculate sum	0	1	5	-4 + (-1) + 2 = -3	[]	sum < 0, move left right	[-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 right	[-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 right	[-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 right	[-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	-	[]	-	[-4, -1, -1, 0, 1, 2]
12	Calculate sum	1	2	5	-1 + (-1) + 2 = 0	[[-1, -1, 2]]	sum == 0, record triplet, move left and right skipping duplicates	[-4, -1, -1, 0, 1, 2]
13	Move left	1	3	5	-	[[-1, -1, 2]]	left=3	[-4, -1, -1, 0, 1, 2]
14	Move right	1	3	4	-	[[-1, -1, 2]]	right=4	[-4, -1, -1, 0, 1, 2]
15	Calculate sum	1	3	4	-1 + 0 + 1 = 0	[[-1, -1, 2], [-1, 0, 1]]	sum == 0, record triplet, move left and right skipping duplicates	[-4, -1, -1, 0, 1, 2]
16	Move left	1	4	3	-	[[-1, -1, 2], [-1, 0, 1]]	left=4	[-4, -1, -1, 0, 1, 2]
17	left >= right, move i	2	3	5	-	[[-1, -1, 2], [-1, 0, 1]]	-	[-4, -1, -1, 0, 1, 2]
18	Skip duplicate i=2 (same as i=1)	3	4	5	-	[[-1, -1, 2], [-1, 0, 1]]	skip i=2	[-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 left	[-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, move i	4	5	5	-	[[-1, -1, 2], [-1, 0, 1]]	-	[-4, -1, -1, 0, 1, 2]
22	End loop	-	-	-	-	[[-1, -1, 2], [-1, 0, 1]]	-	All i processed

💡 All elements processed, no more triplets found

Variable Tracker

Variable	Start	After Step 2	After Step 12	After Step 15	After Step 21	Final
i	-	0	1	1	4	-
left	-	1	2	3	5	-
right	-	5	5	4	5	-
Sum	-	-	0	0	3	-
Triplets Found	[]	[]	[[-1, -1, 2]]	[[-1, -1, 2], [-1, 0, 1]]	[[-1, -1, 2], [-1, 0, 1]]	[[-1, -1, 2], [-1, 0, 1]]

Key Moments - 3 Insights

Why do we move both left and right pointers after finding a triplet?

Because after finding a triplet summing to zero (sum == 0), we must move both pointers to find new triplets and skip duplicates. See steps 12-15 in execution_table where both pointers move after recording triplets.

Why do we skip duplicate i values?

Skipping duplicate i values avoids repeated triplets. In step 18, i=2 is skipped because nums[2] equals nums[1], preventing duplicate triplets.

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

Because the array is sorted, if sum < 0, increasing left pointer moves to a larger number to increase sum; if sum > 0, decreasing right pointer moves to a smaller number to decrease sum. See steps 3-10 and 19-20.

Visual Quiz - 3 Questions

Look at the execution_table at step 12. What is the triplet found?

A [-1, 0, 1]

B [-1, -1, 2]

C [0, 1, 2]

D [-4, 1, 2]

💡 Hint

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

At which step does the left pointer first move to index 4?

A Step 4

B Step 13

C Step 8

D Step 15

💡 Hint

Look at the 'left' column and 'Pointer Moves' in execution_table rows

If the array was not sorted, which part of the execution_table would be invalid?

A Pointer moves based on sum comparisons

B Recording triplets when sum == 0

C Skipping duplicate i values

D Setting initial i, left, right pointers

💡 Hint

Pointer moves rely on sorted array to decide moving left or right

Concept Snapshot

Three Sum Problem:
- Sort the 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, record triplet and move both pointers skipping duplicates
- If sum < 0, move left pointer rightwards
- If sum > 0, move right pointer leftwards
- Skip duplicate i values to avoid repeated 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 efficient two-pointer scanning. For each element i, two pointers left and right scan the remaining array. The sum of nums[i], nums[left], and nums[right] is calculated. If the sum is zero, the triplet is recorded, and both pointers move inward skipping duplicates. If the sum is less than zero, the left pointer moves right to increase the sum. If the sum is greater than zero, the right pointer moves left to decrease the sum. Duplicate i values are skipped to avoid repeated triplets. This process continues until all elements are processed. The execution table traces each step, showing pointer positions, sums, and triplets found, helping visualize how the algorithm works.

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. Find the triplet with the smallest product

D. Find pairs that sum to zero

Solution

1. Step 1: Understand the problem statement

   The problem asks to find all unique sets of three numbers in the array whose sum equals zero.

2. Step 2: Clarify uniqueness and sum condition

   Each triplet must be unique (no duplicates) and the sum of the three numbers must be exactly zero.

3. Final Answer:

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

4. Quick Check:

   Unique triplets with sum zero = Find all unique triplets that sum to zero [OK]

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

Common Mistakes:

• Confusing pairs with triplets
• Ignoring uniqueness of triplets
• Looking for max or min sums instead of zero sum

2. Which of the following C++ code snippets correctly sorts the input vector nums before applying the two-pointer technique in the Three Sum problem?

easy

A. std::sort(nums);

B. sort(nums, nums + nums.size());

C. nums.sort();

D. std::sort(nums.begin(), nums.end());

Solution

1. Step 1: Identify correct sorting syntax for std::vector

   For a vector, sorting requires iterators: nums.begin() and nums.end().

2. Step 2: Check each option

   std::sort(nums.begin(), nums.end()); uses correct syntax. sort(nums, nums + nums.size()); is invalid because nums is a vector, not a pointer array. nums.sort(); is invalid because vector has no sort() method. std::sort(nums); is invalid because std::sort requires two iterators.

3. Final Answer:

   std::sort(nums.begin(), nums.end()); -> Option D

4. Quick Check:

   Correct vector sorting = std::sort(nums.begin(), nums.end()); [OK]

Hint: Use iterators with std::sort for vectors [OK]

Common Mistakes:

• Using pointer syntax on vectors
• Calling sort() as a vector method
• Passing only one argument to std::sort

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

std::vector<int> nums = {-1, 0, 1, 2, -1, -4};
std::vector result;
std::sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; i++) {
  if (i > 0 && nums[i] == nums[i-1]) continue;
  int left = i + 1, right = nums.size() - 1;
  while (left < right) {
    int sum = nums[i] + nums[left] + nums[right];
    if (sum == 0) {
      result.push_back({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--;
    }
  }
}
for (auto &triplet : result) {
  for (int num : triplet) std::cout << num << ' ';
  std::cout << '\n';
}

medium

A. No output

B. -1 -1 2
-1 0 1

C. -4 -1 2
-1 0 1

D. -1 0 1
0 1 2

Solution

1. Step 1: Sort the array and initialize pointers

   Sorted array: [-4, -1, -1, 0, 1, 2]. Loop through each element with two pointers to find triplets summing to zero.

2. Step 2: Identify unique triplets with sum zero

   Triplets found are [-1, -1, 2] and [-1, 0, 1]. These are printed line by line.

3. Final Answer:

   -1 -1 2 -1 0 1 -> Option B

4. Quick Check:

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

Hint: Sort first, then use two pointers to find zero sum triplets [OK]

Common Mistakes:

• Not skipping duplicates
• Incorrect pointer movement
• Printing wrong triplets

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

std::vector<int> nums = {-2, 0, 1, 1, 2};
std::vector result;
std::sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; i++) {
  int left = i + 1, right = nums.size() - 1;
  while (left < right) {
    int sum = nums[i] + nums[left] + nums[right];
    if (sum == 0) {
      result.push_back({nums[i], nums[left], nums[right]});
      left++;
      right--;
    } else if (sum < 0) {
      left++;
    } else {
      right--;
    }
  }
}

medium

A. Missing check to skip duplicate i values

B. Incorrect sorting of the input vector

C. Wrong initialization of pointers left and right

D. Using push_back instead of emplace_back

Solution

1. Step 1: Analyze duplicate handling for i

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

2. Step 2: Confirm other parts are correct

   Sorting is correct, pointers are initialized properly, and push_back is valid here.

3. Final Answer:

   Missing check to skip duplicate i values -> Option A

4. Quick Check:

   Skipping duplicates for i avoids repeated triplets [OK]

Hint: Always skip duplicate i to avoid repeated triplets [OK]

Common Mistakes:

• Not skipping duplicates for i
• Skipping duplicates only for pointers
• Assuming sorting fixes duplicates automatically

5. Given the input array nums = {0, 0, 0, 0}, what is the correct output of the Three Sum problem that finds all unique triplets summing to zero?

hard

A. []

B. [[0, 0, 0], [0, 0, 0]]

C. [[0, 0, 0]]

D. [[0, 0]]

Solution

1. Step 1: Understand the input with duplicates

   All elements are zero, so the only triplet summing to zero is [0, 0, 0].

2. Step 2: Ensure uniqueness of triplets

   Even though multiple zeros exist, only one unique triplet [0, 0, 0] should be returned.

3. Final Answer:

   [[0, 0, 0]] -> Option C

4. Quick Check:

   Unique triplet with zeros = [[0, 0, 0]] [OK]

Hint: Multiple zeros produce one unique triplet [OK]

Common Mistakes:

• Returning duplicate triplets
• Returning pairs instead of triplets
• Returning empty result for all zeros