Three Sum Problem All Unique Triplets in DSA Typescript - 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. We want to list all such triplets without repeating any. This problem helps us practice searching and sorting techniques.

Why it matters

Without a method to find these triplets efficiently, checking every possible group would take too long, especially for big lists. This problem shows how sorting and smart searching can save time. It is a foundation for solving many real-world problems where combinations matter, like finding sets of transactions that balance out.

Where it fits

Before this, you should know arrays, loops, and sorting basics. After this, you can learn about two-pointer techniques, hashing for faster lookups, and more complex combination problems like Four Sum or k-Sum.

Mental Model

Core Idea

Sort the list, then for each number, use two pointers to find pairs that sum to the negative of that number, skipping duplicates to get unique triplets.

Think of it like...

Imagine you have a sorted list of weights on a scale. You pick one weight and then try to find two other weights that together balance it out to zero, moving inward from both ends to find the perfect match.

Sorted array: [-4, -1, -1, 0, 1, 2]
For each element (i):
  i -> fixed number
  left -> i+1
  right -> end
Move left and right pointers:
  If sum < 0, move left rightwards
  If sum > 0, move right leftwards
  If sum == 0, record triplet and skip duplicates

Example:
 i=1 (-1)
 left=2 (-1), right=5 (2)
 sum = -1 + (-1) + 2 = 0 -> triplet found
 Move left and right skipping duplicates

Result triplets:
[-1, -1, 2]
[-1, 0, 1]

Build-Up - 7 Steps

1

Foundation

Understanding the Problem Statement

Concept: Learn what the Three Sum Problem asks for and what unique triplets mean.

We have a list of numbers. We want to find all groups of three numbers that add up to zero. Each group should be unique, meaning no repeated triplets even if numbers appear multiple times.

Result

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

Understanding the problem fully prevents confusion about duplicates and the goal of summing to zero.

2

Foundation

Brute Force Approach and Its Limits

Concept: Try every possible group of three numbers and check their sum.

We can pick every combination of three numbers using three loops and check if they sum to zero. But this takes a lot of time: if the list has n numbers, this is about n³ checks.

Result

Brute force works but is very slow for large lists.

Knowing brute force helps appreciate why we need smarter methods to save time.

3

Intermediate

Sorting the Array to Simplify Searching

Concept: Sort the list to make it easier to find pairs that sum to a target.

Sorting arranges numbers from smallest to largest. This order helps us use two pointers to find pairs quickly. For example, if the sum is too small, we move the left pointer right to increase sum; if too big, move right pointer left to decrease sum.

Result

Sorted array allows efficient searching for pairs.

Sorting transforms the problem into a structure where two-pointer technique becomes possible.

4

Intermediate

Two-Pointer Technique for Pair Finding

🤔Before reading on: do you think moving both pointers inward always finds all pairs? Commit to yes or no.

Concept: Use two pointers starting at both ends of the array segment to find pairs that sum to a target value.

Fix one number, then set left pointer just after it and right pointer at the end. Calculate sum of fixed + left + right. If sum is less than zero, move left pointer right to increase sum. If sum is more than zero, move right pointer left to decrease sum. If sum is zero, record triplet and move both pointers skipping duplicates.

Result

Pairs that sum to the negative of the fixed number are found efficiently.

Two-pointer technique reduces pair search from O(n²) to O(n), making the overall solution much faster.

5

Intermediate

Skipping Duplicates to Ensure Unique Triplets

🤔Before reading on: do you think skipping duplicates is necessary to avoid repeated triplets? Commit to yes or no.

Concept: Avoid counting the same triplet multiple times by skipping repeated numbers during iteration and pointer moves.

After sorting, duplicates appear next to each other. When moving pointers or the main loop index, skip over numbers equal to the previous one. This prevents adding the same triplet multiple times.

Result

Only unique triplets are recorded, no repeats.

Skipping duplicates is key to meeting the problem's requirement of unique triplets.

6

Advanced

Complete TypeScript Implementation with Comments

🤔Before reading on: do you think the two-pointer method can be implemented cleanly in TypeScript with proper types? Commit to yes or no.

Concept: Write a full TypeScript function that finds all unique triplets using sorting and two pointers.

function threeSum(nums: number[]): number[][] { nums.sort((a, b) => a - b); const result: number[][] = []; for (let i = 0; i < nums.length - 2; i++) { if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicates let left = i + 1; let right = nums.length - 1; while (left < right) { const sum = nums[i] + nums[left] + nums[right]; if (sum === 0) { result.push([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--; } } } return result; }

Result

Function returns all unique triplets that sum to zero.

Seeing the full code connects all concepts and shows how to implement the solution practically.

7

Expert

Time Complexity and Optimization Insights

🤔Before reading on: do you think the overall time complexity is O(n^2) or O(n^3)? Commit to your answer.

Concept: Analyze why sorting plus two-pointer scanning leads to O(n^2) time, and understand the limits of optimization.

Sorting takes O(n log n). The main loop runs O(n) times. For each, two pointers scan the rest in O(n). So total is O(n log n + n^2) which is O(n^2). This is much better than brute force O(n^3). Further optimization is hard because we must check pairs for each fixed number.

Result

Understanding the solution is efficient and near optimal for this problem.

Knowing the complexity helps set expectations and guides when to use this approach or seek approximate methods.

Under the Hood

The algorithm first sorts the array to arrange numbers in order. Then it fixes one number and uses two pointers to scan the remaining part for pairs that sum to the negative of the fixed number. Skipping duplicates ensures unique triplets. Internally, sorting uses efficient algorithms like quicksort or mergesort. The two-pointer technique exploits the sorted order to move pointers inward based on sum comparisons, avoiding unnecessary checks.

Why designed this way?

Sorting enables the two-pointer method, which is much faster than brute force. Early solutions tried all triplets, but that was too slow. The two-pointer approach was designed to reduce complexity by leveraging order. Skipping duplicates was added to meet the problem's uniqueness requirement without extra memory.

Input array
  ↓ sort
Sorted array
  ↓ fix one element (i)
Two pointers (left, right) scan inward
  ↔ move pointers based on sum
  ↔ skip duplicates
  ↓ collect triplets
Output: unique triplets

+-------------------+
| Sorted Array      |
| [-4, -1, -1, 0, 1, 2] |
+-------------------+
        ↓
+-------------------+
| Fix i = -1        |
+-------------------+
        ↓
+-------------------+
| left = i+1, right = end |
+-------------------+
        ↓
+-------------------+
| sum = i + left + right |
| if sum < 0 → left++    |
| if sum > 0 → right--   |
| if sum == 0 → record   |
+-------------------+

Myth Busters - 4 Common Misconceptions

Quick: Do you think sorting the array is optional for solving Three Sum efficiently? Commit to yes or no.

Common Belief: Some think you can find all triplets efficiently without sorting by just using hash sets.

Reality: Sorting is essential for the two-pointer technique, which is the most efficient known method. Hash sets alone don't guarantee unique triplets or efficient scanning.

Why it matters: Skipping sorting leads to slower solutions or complicated duplicate handling, making the code inefficient and error-prone.

Quick: Do you think the two-pointer method can find triplets if the array is unsorted? Commit to yes or no.

Common Belief: People often believe two pointers work even if the array is not sorted.

Reality: Two-pointer technique requires a sorted array to decide pointer moves based on sum comparisons.

Why it matters: Using two pointers on unsorted data leads to incorrect results or missed triplets.

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

Common Belief: Many assume duplicates in input always cause duplicate triplets in output.

Reality: With proper skipping of duplicates during iteration and pointer moves, output triplets remain unique despite input duplicates.

Why it matters: Failing to skip duplicates causes repeated triplets, violating problem requirements and confusing users.

Quick: Do you think the time complexity of the best solution is O(n log n)? Commit to yes or no.

Common Belief: Some believe sorting dominates time, so overall complexity is O(n log n).

Reality: The two-pointer scanning inside the loop leads to O(n^2) complexity, which dominates sorting time.

Why it matters: Underestimating complexity can cause wrong performance expectations and poor algorithm choices.

Expert Zone

1

The order of skipping duplicates is critical: skipping duplicates for the fixed element and for the left and right pointers must be done carefully to avoid missing valid triplets or adding duplicates.

2

When the input array contains many duplicates, the algorithm's performance can degrade due to repeated skipping steps, but it still remains O(n^2).

3

The problem can be extended to k-Sum by recursively applying the two-pointer approach, but complexity grows exponentially, so Three Sum is a sweet spot for this technique.

When NOT to use

Avoid this approach if the input size is extremely large and approximate answers are acceptable; then use hashing with early stopping or probabilistic methods. Also, if the problem changes to find triplets summing to a number other than zero, the method still works but requires adjusting the target sum accordingly.

Production Patterns

In production, this pattern is used in financial fraud detection to find sets of transactions that balance out, in recommendation systems to find groups of items with combined properties, and in coding interviews as a classic problem to test sorting and two-pointer skills.

Connections

Two Sum Problem

Builds-on

Understanding Two Sum helps grasp the pair-finding step inside Three Sum, as Three Sum fixes one number and reduces the problem to Two Sum on the rest.

Sorting Algorithms

Depends-on

Knowing sorting algorithms is crucial because the efficiency of Three Sum relies on the array being sorted to apply the two-pointer technique.

Chemical Reaction Balancing

Analogous pattern

Balancing chemical equations involves finding sets of coefficients that sum to zero net change, similar to finding triplets summing to zero, showing how math patterns appear in chemistry.

Common Pitfalls

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

Wrong approach:

for (let i = 0; i < nums.length - 2; i++) {
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
if (nums[i] + nums[left] + nums[right] === 0) {
result.push([nums[i], nums[left], nums[right]]);
left++;
right--;
} else if (nums[i] + nums[left] + nums[right] < 0) {
left++;
} else {
right--;
}
}
}

Correct approach:

for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([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--;
}
}
}

Root cause:

Not handling duplicates properly causes the same triplet to be added multiple times.

#2 Using two pointers without sorting the array.

Wrong approach:

const nums = [1, 0, -1, 2, -2];
let left = 0;
let right = nums.length - 1;
while (left < right) {
// attempt two-pointer logic without sorting
}

Correct approach:

nums.sort((a, b) => a - b);
let left = 0;
let right = nums.length - 1;
while (left < right) {
// two-pointer logic works correctly
}

Root cause:

Two-pointer technique relies on sorted order to decide pointer moves.

#3 Assuming the problem is solved by just finding any three numbers summing to zero once.

Wrong approach:

Stop after finding the first triplet that sums to zero without searching for others.

Correct approach:

Continue scanning all possible triplets to find all unique triplets that sum to zero.

Root cause:

Misunderstanding the problem requirement to find all unique triplets, not just one.

Key Takeaways

The Three Sum Problem finds all unique triplets in a list that add up to zero by sorting and using two pointers.

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

Skipping duplicates during iteration and pointer movement ensures the output contains only unique triplets.

The overall time complexity is O(n^2), which is much faster than brute force O(n^3) and near optimal for this problem.

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 array of integers?

easy

A. Find the maximum sum of any three numbers

B. Find all unique triplets that sum to zero

C. Find the three largest numbers in the array

D. Find pairs of numbers that sum to zero

Solution

1. Step 1: Understand the problem requirement

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

2. Step 2: Differentiate from other sum problems

   Unlike finding pairs or maximum sums, this problem specifically looks for triplets with sum zero and no duplicates.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Confusing with pair sum problems
• Looking for maximum sum instead of zero sum
• Ignoring uniqueness of triplets

2. Which of the following TypeScript function signatures correctly represents a function solving the Three Sum Problem returning all unique triplets as arrays?

easy

A. function threeSum(nums: number[]): number[][]

B. function threeSum(nums: number): number[]

C. function threeSum(nums: string[]): string[][]

D. function threeSum(nums: number[][]): number[]

Solution

1. Step 1: Analyze the input parameter type

   The input should be an array of numbers, so nums: number[] is correct.

2. Step 2: Analyze the return type

   The function returns an array of triplets, each triplet is an array of numbers, so number[][] is correct.

3. Final Answer:

   function threeSum(nums: number[]): number[][] -> Option A

4. Quick Check:

   Input array of numbers, output array of number triplets [OK]

Hint: Input array of numbers, output array of triplets [OK]

Common Mistakes:

• Using wrong input type like single number or string array
• Returning flat array instead of array of arrays
• Confusing input and output types

3. What is the output of the following TypeScript code snippet?

const nums = [-1, 0, 1, 2, -1, -4];
function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);
  const result: number[][] = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum === 0) {
        result.push([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--;
      }
    }
  }
  return result;
}
console.log(threeSum(nums));

medium

A. [[-1, 0, 1], [0, 1, 2]]

B. [[-4, 0, 4], [-1, -1, 2]]

C. [[-1, -1, 2], [-1, 0, 1]]

D. [[0, 1, 2], [-1, -1, 2]]

Solution

1. Step 1: Sort the array

   Sorted array is [-4, -1, -1, 0, 1, 2].

2. Step 2: Find unique triplets summing to zero

   Triplets found are [-1, -1, 2] and [-1, 0, 1].

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: Sort array, use two pointers to find triplets [OK]

Common Mistakes:

• Not sorting array before processing
• Including duplicate triplets
• Incorrect pointer movement causing wrong sums

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

function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);
  const result: number[][] = [];
  for (let i = 0; i < nums.length - 2; i++) {
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);
        left++;
        right--;
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }
  return result;
}

medium

A. Missing check to skip duplicate 'i' values

B. Incorrect sorting order of the array

C. Wrong initialization of left and right pointers

D. Returning result before loop ends

Solution

1. Step 1: Check for duplicate skipping

   The code does not skip duplicate values for index i, which can cause duplicate triplets.

2. Step 2: Confirm other parts are correct

   Sorting is correct ascending, pointers initialized properly, and return is after loops.

3. Final Answer:

   Missing check to skip duplicate 'i' values -> Option A

4. Quick Check:

   Duplicate skipping for i missing = bug [OK]

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

Common Mistakes:

• Not skipping duplicates for i index
• Skipping duplicates only for left or right pointers
• Incorrect pointer initialization

5. Given the array nums = [-2, 1, 0, -1, 2, -3], which of the following is the correct set of all unique triplets that sum to zero?

hard

A. [[-3, 0, 3], [-2, -1, 3], [-2, 0, 2], [-1, 0, 1]]

B. [[-3, 1, 2], [-2, -1, 3], [-1, 0, 1]]

C. [[-3, 0, 3], [-2, -1, 3], [-1, 0, 1]]

D. [[-3, 1, 2], [-2, 0, 2], [-1, 0, 1]]

Solution

1. Step 1: Sort the array

   Sorted array is [-3, -2, -1, 0, 1, 2].

2. Step 2: Find all unique triplets summing to zero

   Triplets are [-3, 1, 2], [-2, 0, 2], and [-1, 0, 1].

3. Final Answer:

   [[-3, 1, 2], [-2, 0, 2], [-1, 0, 1]] -> Option D

4. Quick Check:

   All unique triplets summing zero = [[-3,1,2],[-2,0,2],[-1,0,1]] [OK]

Hint: Sort and check pairs with two pointers for zero sum [OK]

Common Mistakes:

• Including triplets with wrong sums
• Missing valid triplets
• Including duplicates or invalid triplets