Three Sum Problem All Unique Triplets in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to sort the input vector before processing.

DSA C++

std::sort(nums.begin(), nums.[1]());

Drag options to blanks, or click blank then click option'

Aend

Brbegin

Cbegin

Drend

Attempts:

3 left

💡 Hint

Common Mistakes

Using rbegin() or rend() which are reverse iterators and cause errors.

Forgetting to sort the vector before processing.

We need to sort the vector from begin() to end() to process elements in order.

2fill in blank

medium

Complete the code to skip duplicate elements for the first pointer i.

DSA C++

if (i > 0 && nums[i] == nums[[1]]) continue;

Drag options to blanks, or click blank then click option'

Ai + 1

Bi - 1

C0

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with nums[i+1] which may go out of bounds.

Not checking i > 0 before accessing nums[i-1].

We compare current element nums[i] with the previous nums[i-1] to skip duplicates.

3fill in blank

hard

Fix the error in the while loop condition to move the left pointer correctly.

DSA C++

while (left < right && nums[left] == nums[[1]]) left++;

Drag options to blanks, or click blank then click option'

Aleft + 1

Bright

Cleft - 1

Dright - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with nums[left + 1] which is not yet moved.

Comparing with nums[right] which is unrelated here.

We compare nums[left] with nums[left - 1] to skip duplicates after incrementing left.

4fill in blank

hard

Fill both blanks to correctly move the right pointer and skip duplicates.

DSA C++

while (left < right && nums[right] == nums[[1]]) [2];

Drag options to blanks, or click blank then click option'

Aright + 1

Bright - 1

Cleft++

Dright--

Attempts:

3 left

💡 Hint

Common Mistakes

Incrementing right pointer which goes out of bounds.

Comparing with left pointer values.

We compare nums[right] with nums[right - 1] and decrement right to skip duplicates.

5fill in blank

hard

Fill all three blanks to correctly update pointers based on sum comparison.

DSA C++

if (sum < 0) [1];
else if (sum > 0) [2];
else {
    result.push_back({nums[i], nums[left], nums[right]});
    [3];
}

Drag options to blanks, or click blank then click option'

Aleft++

Bright--

Cleft++; right--

Di++

Attempts:

3 left

💡 Hint

Common Mistakes

Moving wrong pointers for sum comparison.

Not moving both pointers after finding a valid triplet.

If sum is less than zero, move left pointer right to increase sum; if greater, move right pointer left to decrease sum; if equal, add triplet and move both pointers.

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