Three Sum Problem All Unique Triplets in DSA C++ - Deep Dive

Overview - Three Sum Problem All Unique Triplets

What is it?

The Three Sum Problem asks us to find all unique groups of three numbers in a list that add up to zero. Each group is called a triplet, and no two triplets should be the same. This problem helps us understand how to efficiently search and combine elements in a list to meet a condition.

Why it matters

Without a method to find these triplets, checking every possible group would take too long, especially with big lists. This problem teaches us how to reduce unnecessary work and avoid duplicates, which is important in many real-world tasks like finding combinations or patterns in data.

Where it fits

Before this, you should know how to sort lists and use two-pointer techniques. After mastering this, you can learn more complex problems like k-sum or subset sum, which build on similar ideas of combining elements efficiently.

Mental Model

Core Idea

Find three numbers that sum to zero by sorting the list and using two pointers to efficiently explore pairs for each fixed number.

Think of it like...

Imagine you have a sorted row of books with different thicknesses. You pick one book and then try to find two others that together balance perfectly on a scale at zero. You move your hands inward from both ends to find the right pair quickly.

Sorted array: [-4, -1, -1, 0, 1, 2]
Fix one element (i):
  i -> -4
Two pointers:
  left -> start just after i
  right -> end of array
Move pointers based on sum:
  sum = nums[i] + nums[left] + nums[right]
If sum < 0: move left rightwards
If sum > 0: move right leftwards
If sum == 0: record triplet and move both pointers skipping duplicates

Build-Up - 6 Steps

1

Foundation

Understanding the Problem Statement

Concept: Learn what the problem asks: find all unique triplets that sum to zero.

Given an array of integers, we want to find all sets of three numbers where their sum is zero. For example, in [-1, 0, 1, 2, -1, -4], the triplets are [-1, -1, 2] and [-1, 0, 1]. We must avoid repeating the same triplet twice.

Result

Clear understanding of the goal: find unique triplets summing to zero.

Understanding the exact problem prevents confusion and guides how to approach the solution.

2

Foundation

Sorting the Array to Simplify Searching

Concept: Sort the array to make it easier to find pairs and avoid duplicates.

Sorting the array arranges numbers from smallest to largest. For example, [-1, 0, 1, 2, -1, -4] becomes [-4, -1, -1, 0, 1, 2]. This order helps us use two pointers to find pairs that sum to a target efficiently.

Result

Sorted array: [-4, -1, -1, 0, 1, 2]

Sorting transforms the problem into a structured search, enabling faster and simpler pair finding.

3

Intermediate

Using Two Pointers to Find Pairs

🤔Before reading on: do you think checking all pairs with two pointers is faster than nested loops? Commit to your answer.

Concept: Use two pointers moving inward from both ends to find pairs that sum to a target value.

For each fixed number, set two pointers: one just after it (left) and one at the end (right). Calculate the sum of the fixed number and the two pointers. If the sum is less than zero, move left pointer right to increase sum. If more than zero, move right pointer left to decrease sum. If zero, record the triplet and move both pointers skipping duplicates.

Result

Pairs found efficiently without checking every combination.

Two pointers reduce time complexity from O(n^2) to O(n) for pair searching, making the overall solution faster.

4

Intermediate

Skipping Duplicates to Ensure Unique Triplets

🤔Before reading on: do you think duplicates in the array will cause repeated triplets? Commit to yes or no.

Concept: Avoid repeating the same triplet by skipping duplicate numbers during iteration and pointer movement.

After sorting, duplicates appear next to each other. When fixing a number, if it is the same as the previous fixed number, skip it. Similarly, after finding a valid triplet, move left and right pointers past any duplicates to avoid repeating the same triplet.

Result

Only unique triplets are collected.

Skipping duplicates prevents redundant work and ensures the output contains only distinct triplets.

5

Advanced

Implementing Complete Three Sum Algorithm in C++

🤔Before reading on: do you think the algorithm runs in O(n^3) or better? Commit to your answer.

Concept: Combine sorting, fixing one element, and two-pointer search to find all unique triplets efficiently.

#include #include std::vector> threeSum(std::vector& nums) { std::vector> result; std::sort(nums.begin(), nums.end()); int n = nums.size(); for (int i = 0; i < n - 2; ++i) { if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates int left = i + 1, right = n - 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; // skip duplicates while (left < right && nums[right] == nums[right - 1]) --right; // skip duplicates ++left; --right; } else if (sum < 0) { ++left; } else { --right; } } } return result; }

Result

All unique triplets summing to zero are found in O(n^2) time.

Combining sorting and two-pointer technique achieves efficient search and uniqueness in one pass.

6

Expert

Optimizing and Handling Edge Cases in Three Sum

🤔Before reading on: do you think early stopping when fixed number > 0 improves performance? Commit yes or no.

Concept: Add optimizations like early stopping and careful edge case handling to improve performance and correctness.

Since the array is sorted, if the fixed number is greater than zero, no triplet can sum to zero because all numbers after are also positive. We can stop early. Also, handle cases with fewer than three numbers by returning empty results immediately. These small checks save time and avoid errors.

Result

Faster execution and robust handling of all input cases.

Knowing problem constraints and input properties allows smart shortcuts that improve real-world performance.

Under the Hood

The algorithm first sorts the array to arrange numbers in order. Then, it fixes one number at a time and uses two pointers to find pairs that sum to the negative of the fixed number. Moving pointers inward adjusts the sum efficiently without checking all pairs. Skipping duplicates ensures unique triplets. Internally, sorting takes O(n log n), and the two-pointer search runs in O(n) for each fixed number, resulting in O(n^2) overall.

Why designed this way?

Brute force checking all triplets would take O(n^3), which is too slow for large inputs. Sorting enables the two-pointer technique, which reduces pair searching to O(n). Skipping duplicates avoids repeated work and output. This design balances simplicity, speed, and correctness.

Input array
  ↓ sort
Sorted array: ┌─────────────┐
              │ -4 -1 -1 0 1 2 │
              └─────────────┘
For each i: fix nums[i]
  ┌───────────────┐
  │ i = 0 (-4)    │
  └───────────────┘
Two pointers:
  left -> i+1, right -> end
  Move pointers based on sum:
  sum = nums[i] + nums[left] + nums[right]
  ┌─────────────┐
  │ sum < 0 -> left++ │
  │ sum > 0 -> right--│
  │ sum = 0 -> record │
  └─────────────┘
Skip duplicates when moving i, left, right

Myth Busters - 4 Common Misconceptions

Quick: Do you think sorting the array changes the final triplets found? Commit yes or no.

Common Belief: Sorting the array might change the triplets or lose some solutions.

Reality: Sorting only rearranges elements but does not remove or change values, so all valid triplets remain and can be found more easily.

Why it matters: Believing sorting changes results might prevent learners from using the most efficient approach, leading to slower or incorrect solutions.

Quick: Do you think checking every possible triplet is the only way to solve this? Commit yes or no.

Common Belief: The only way to find all triplets is to check every combination of three numbers.

Reality: Using sorting and two pointers reduces the search space drastically, avoiding unnecessary checks and improving performance from O(n^3) to O(n^2).

Why it matters: Not knowing efficient methods leads to slow code that can't handle large inputs.

Quick: Do you think duplicates in the input always produce duplicate triplets? Commit yes or no.

Common Belief: If the input has duplicates, the output will have duplicate triplets.

Reality: By skipping duplicates during iteration and pointer movement, the algorithm ensures only unique triplets are included.

Why it matters: Failing to handle duplicates causes repeated results, which is incorrect and wastes resources.

Quick: Do you think the two-pointer technique works without sorting? Commit yes or no.

Common Belief: Two-pointer method can be applied directly on unsorted arrays.

Reality: Two-pointer technique requires a sorted array to move pointers logically based on sum comparisons.

Why it matters: Applying two pointers on unsorted data leads to incorrect results and confusion.

Expert Zone

1

Skipping duplicates must be done carefully both when fixing the first element and when moving left and right pointers to avoid missing valid triplets or including duplicates.

2

Early stopping when the fixed number is positive saves time because no further triplets can sum to zero beyond that point.

3

The algorithm can be adapted to find triplets summing to any target by adjusting the sum comparison, showing its flexibility.

When NOT to use

This approach is not suitable if the input is extremely large and cannot be sorted in memory, or if the problem requires counting triplets without listing them. Alternatives include hash-based methods or approximate algorithms.

Production Patterns

In real systems, this pattern is used in financial fraud detection to find suspicious combinations, in recommendation engines to find item sets, and in coding interviews to test problem-solving and optimization skills.

Connections

Two Sum Problem

Three Sum builds on Two Sum by fixing one element and searching pairs that sum to a target.

Understanding Two Sum's pair-finding logic is essential to grasping how Three Sum extends it to triplets.

Sorting Algorithms

Sorting is a prerequisite step that enables efficient searching techniques like two pointers.

Knowing sorting algorithms helps appreciate why sorted data allows linear-time pair searches.

Chemical Reaction Balancing

Both involve finding combinations of elements that satisfy a sum or balance condition.

Recognizing that balancing chemical equations and Three Sum share the idea of combining parts to meet a target helps cross-disciplinary problem solving.

Common Pitfalls

#1 Not sorting the array before applying two pointers.

Wrong approach:

int left = i + 1, right = nums.size() - 1;
// array not sorted
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
// logic assumes sorted array
}

Correct approach:

std::sort(nums.begin(), nums.end());
int left = i + 1, right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
// correct logic
}

Root cause:

Misunderstanding that two-pointer technique requires sorted data to work correctly.

#2 Not skipping duplicates leads to repeated triplets in output.

Wrong approach:

for (int i = 0; i < n - 2; ++i) {
// no check for duplicates
int left = i + 1, right = n - 1;
while (left < right) {
if (sum == 0) {
result.push_back({nums[i], nums[left], nums[right]});
++left; --right;
}
}
}

Correct approach:

for (int i = 0; i < n - 2; ++i) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = n - 1;
while (left < 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;
}
}
}

Root cause:

Not realizing duplicates appear consecutively in sorted arrays and must be skipped to avoid repeated results.

#3 Not handling edge cases like empty or small arrays.

Wrong approach:

std::vector> threeSum(std::vector& nums) {
// no check for size
// proceed directly
}

Correct approach:

if (nums.size() < 3) return {};
// proceed with algorithm

Root cause:

Overlooking input constraints and failing to handle trivial or invalid inputs.

Key Takeaways

Sorting the array is essential to apply the two-pointer technique efficiently.

Fixing one element and searching pairs with two pointers reduces complexity from cubic to quadratic.

Skipping duplicates at every step ensures the output contains only unique triplets.

Early stopping and edge case handling improve performance and robustness.

Understanding this problem builds a foundation for solving more complex combination and sum problems.

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