Three Sum Problem All Unique Triplets in DSA Javascript - 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 have the same numbers. This problem helps us practice searching and combining numbers efficiently.

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 find answers faster, which is important in many real-world tasks like data analysis and software optimization.

Where it fits

Before this, you should understand arrays, sorting, and the two-pointer technique. After mastering this, you can learn more complex problems like k-sum or subset sum, which build on similar ideas.

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 list of weights on a scale. You pick one weight and then try to find two others that balance the scale to zero by moving your hands inward from both ends.

Sorted array: [-4, -1, -1, 0, 1, 2]
Fix one number (index i): -4
Use two pointers (left, right): start at i+1 and end
Move pointers inward to find pairs that sum with fixed number to zero

  i
  ↓
[-4, -1, -1, 0, 1, 2]
     ↑           ↑
   left        right

Build-Up - 7 Steps

1

Foundation

Understanding the Problem Setup

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

Given an array of numbers, we want to find all groups of three numbers where the sum is zero. For example, in [-1, 0, 1, 2, -1, -4], one triplet is [-1, 0, 1]. We must avoid duplicates like [-1, 0, 1] appearing twice.

Result

Clear goal: find all unique triplets summing to zero.

Understanding the problem clearly helps avoid confusion about duplicates and what the output should look like.

2

Foundation

Sorting the Array First

Concept: Sort the array to make searching easier and to handle 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 helps us use two pointers and skip duplicates efficiently.

Result

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

Sorting is a key step that simplifies the problem and enables efficient searching.

3

Intermediate

Fix One Number and Use Two Pointers

🤔Before reading on: do you think fixing one number and searching pairs with two pointers is faster than checking all triplets? Commit to your answer.

Concept: For each number, fix it and find two others that sum to the negative of the fixed number using two pointers.

We loop through the array, fixing one number at a time. Then, we set two pointers: one just after the fixed number (left) and one at the end (right). We check the sum of these three numbers. If the sum is too small, move left pointer right; if too big, move right pointer left. If sum is zero, record the triplet.

Result

Efficiently finds triplets without checking every combination.

Using two pointers after sorting reduces the problem from O(n^3) to O(n^2), a big speedup.

4

Intermediate

Skipping Duplicates to Ensure Uniqueness

🤔Before reading on: do you think skipping duplicates is necessary to avoid repeated triplets? Commit to your answer.

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

When the fixed number is the same as the previous one, skip it. Also, 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 is clean and correct.

5

Intermediate

Handling Edge Cases and Empty Results

Concept: Consider cases like empty arrays, arrays with fewer than three numbers, or no triplets found.

If the array has less than three numbers, return empty list immediately. If no triplets sum to zero, return empty list. This avoids errors and clarifies expected output.

Result

Robust function that handles all inputs gracefully.

Thinking about edge cases early prevents bugs and unexpected crashes.

6

Advanced

Complete JavaScript Implementation

🤔Before reading on: predict the output of the code for input [-1,0,1,2,-1,-4]. Commit to your answer.

Concept: Putting all ideas together into a working JavaScript function.

function threeSum(nums) { if (nums.length < 3) return []; nums.sort((a, b) => a - b); const result = []; for (let i = 0; i < nums.length - 2; i++) { if (i > 0 && nums[i] === nums[i - 1]) continue; if (nums[i] > 0) break; 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; } // Example usage: console.log(threeSum([-1,0,1,2,-1,-4]));

Result

[[-1, -1, 2], [-1, 0, 1]]

Seeing the full code helps connect all concepts and shows how they work together in practice.

7

Expert

Optimizations and Time Complexity Insights

🤔Before reading on: do you think the algorithm always runs in O(n^2) time? Commit to your answer.

Concept: Understand the time complexity and possible optimizations like early stopping and pruning.

The main loop runs O(n) times, and the two-pointer search inside runs O(n), so total is O(n^2). Early stopping can happen if the fixed number is positive since no triplet can sum to zero beyond that. Also, pruning can skip unnecessary checks when sums exceed zero.

Result

Algorithm runs efficiently with O(n^2) time, better than brute force O(n^3).

Knowing complexity and optimizations helps write faster code and understand limits.

Under the Hood

The algorithm sorts the array to arrange numbers in order. Then, for each fixed number, it uses two pointers moving inward to find pairs that sum to the negative of the fixed number. This works because the array is sorted, so moving pointers adjusts the sum predictably. Skipping duplicates avoids repeated triplets. Internally, this reduces the number of checks drastically compared to brute force.

Why designed this way?

Sorting and two pointers were chosen because they allow linear-time pair searching after sorting. Alternatives like brute force check all triplets (O(n^3)), which is too slow. Hash-based methods exist but can be more complex and use extra space. This method balances speed, simplicity, and memory use.

Input array
  ↓
[unsorted numbers]
  ↓ sort
[sorted numbers]
  ↓
For each index i:
  Fix nums[i]
  Set left = i+1, right = end
  While left < right:
    sum = nums[i] + nums[left] + nums[right]
    If sum == 0: record triplet, move pointers skipping duplicates
    Else if sum < 0: left++
    Else: right--

Myth Busters - 4 Common Misconceptions

Quick: Do you think the order of numbers in triplets matters for uniqueness? Commit yes or no.

Common Belief: People often think triplets like [1, -1, 0] and [-1, 0, 1] are different and should both appear.

Reality: Triplets are considered the same regardless of order, so only one sorted version should be included.

Why it matters: Including duplicates wastes time and confuses results, making the output incorrect.

Quick: Do you think sorting is optional for this problem? Commit yes or no.

Common Belief: Some believe you can find triplets without sorting the array first.

Reality: Sorting is essential for the two-pointer technique and for skipping duplicates efficiently.

Why it matters: Without sorting, the algorithm becomes much slower and more complex.

Quick: Do you think the two-pointer method always finds all triplets? Commit yes or no.

Common Belief: People may think two pointers miss some triplets because it only moves inward from ends.

Reality: Two pointers find all valid pairs for each fixed number because the array is sorted and pointers move to cover all possibilities.

Why it matters: Misunderstanding this can lead to incorrect implementations that miss solutions.

Quick: Do you think the algorithm can stop early once the fixed number is positive? Commit yes or no.

Common Belief: Some think the algorithm must check all numbers regardless of their sign.

Reality: Once the fixed number is positive, no triplet can sum to zero because the array is sorted ascending.

Why it matters: Not stopping early wastes time checking impossible triplets.

Expert Zone

1

The importance of skipping duplicates both when fixing the number and when moving pointers to avoid subtle repeated triplets.

2

Early stopping when the fixed number is greater than zero can reduce runtime significantly on large inputs.

3

Understanding that the two-pointer approach relies on the array being sorted and that any unsorted input breaks the logic.

When NOT to use

This approach is not suitable if the array is extremely large and cannot be sorted efficiently or if the problem requires triplets summing to a number other than zero without modification. Alternatives include hash-based methods or using data structures like balanced trees.

Production Patterns

In real systems, this pattern is used in financial data analysis to find zero-sum transactions, in gaming for score balancing, and in coding interviews to test problem-solving and optimization skills.

Connections

Two Pointer Technique

Builds-on

Mastering the two-pointer technique is essential to efficiently find pairs in sorted arrays, which is the core of the three sum solution.

Sorting Algorithms

Prerequisite

Understanding sorting algorithms helps appreciate why sorting is the first step and how it enables efficient searching.

Chemical Reaction Balancing

Analogous pattern

Balancing chemical equations involves finding combinations of elements that sum to zero net change, similar to finding triplets summing to zero in arrays.

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 (sum < 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 understanding the need to skip duplicates when fixing numbers and moving pointers.

#2 Trying to find triplets without sorting the array first.

Wrong approach:

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

Correct approach:

nums.sort((a, b) => a - b);
// then use two-pointer approach as shown in previous steps

Root cause:

Not realizing sorting is necessary for efficient searching and duplicate handling.

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

Wrong approach:

function threeSum(nums) {
// no check for length
// proceed with logic
}

Correct approach:

function threeSum(nums) {
if (nums.length < 3) return [];
// proceed with logic
}

Root cause:

Overlooking input validation and edge case handling.

Key Takeaways

The Three Sum Problem finds all unique triplets in an array that sum to zero by sorting and using two pointers.

Sorting the array is essential to efficiently find pairs and skip duplicates.

Fixing one number and searching pairs with two pointers reduces time complexity from O(n^3) to O(n^2).

Skipping duplicates during iteration and pointer movement ensures unique triplets without repeats.

Understanding time complexity and edge cases leads to robust and optimized solutions.

Practice

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

easy

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

B. Sort the array in ascending order

C. Find the maximum sum of any three elements

D. Count the number of pairs 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 sum problems

   Unlike sorting or pair sums, this problem specifically targets triplets summing to zero without duplicates.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Confusing with pair sum problems
• Thinking it requires sorting only
• Looking for max sum instead of zero sum

2. Which of the following is the correct way to start sorting an array nums in JavaScript before solving the Three Sum Problem?

easy

A. nums.sort()

B. nums.sorted()

C. nums.sort((a, b) => b - a)

D. nums.sort((a, b) => a - b)

Solution

1. Step 1: Understand JavaScript sort behavior

   By default, sort() converts elements to strings and sorts lexicographically, which is incorrect for numbers.

2. Step 2: Use numeric comparator for ascending order

   Using nums.sort((a, b) => a - b) sorts numbers correctly in ascending order, which is needed for the algorithm.

3. Final Answer:

   nums.sort((a, b) => a - b) -> Option D

4. Quick Check:

   Numeric ascending sort = nums.sort((a, b) => a - b) [OK]

Hint: Use comparator (a, b) => a - b for numeric ascending sort [OK]

Common Mistakes:

• Using default sort() without comparator
• Using descending sort when ascending needed
• Using non-existent method sorted()

3. What will be the output of the following code snippet?

function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const result = [];
  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 (nums[left] === nums[left + 1]) left++;
        while (nums[right] === nums[right - 1]) right--;
        left++;
        right--;
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }
  return result;
}

console.log(threeSum([-1,0,1,2,-1,-4]));

medium

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

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

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

D. [[0, 0, 0]]

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]. These are pushed to result.

3. Final Answer:

   [[-1, -1, 2], [-1, 0, 1]] -> Option B

4. Quick Check:

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

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

Common Mistakes:

• Not sorting before two-pointer approach
• Including duplicate triplets
• Incorrect pointer movement logic

4. Identify the bug in this Three Sum implementation snippet:

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

medium

A. The duplicate check for nums[i] should skip when i > 0

B. The sorting comparator is incorrect

C. The pointers left and right are not updated

D. The result array is not initialized

Solution

1. Step 1: Check duplicate skipping condition

   The condition if (nums[i] === nums[i - 1]) continue; runs even when i = 0, causing incorrect skipping.

2. Step 2: Correct condition to skip duplicates only if i > 0

   It should be if (i > 0 && nums[i] === nums[i - 1]) continue; to avoid skipping first element.

3. Final Answer:

   The duplicate check for nums[i] should skip when i > 0 -> Option A

4. Quick Check:

   Duplicate skip needs i > 0 check [OK]

Hint: Check index bounds when skipping duplicates [OK]

Common Mistakes:

• Skipping duplicates without index check
• Wrong sorting comparator
• Forgetting to update pointers

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

hard

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

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

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

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

Solution

1. Step 1: Sort the array

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

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

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

3. Final Answer:

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

4. Quick Check:

   Sorted + two pointers find unique zero sum triplets [OK]

Hint: Sort and use two pointers to find all zero sum triplets [OK]

Common Mistakes:

• Missing some triplets
• Including duplicates
• Incorrect triplet sums