Three Sum Problem All Unique Triplets in DSA Javascript

Mental Model

Find three numbers in a list that add up to zero without repeating the same triplet.

Analogy: Imagine you have a group of friends with different heights, and you want to find three friends whose heights balance out perfectly to zero when combined, like balancing weights on a scale.

nums: [-4] -> [-1] -> [-1] -> [0] -> [1] -> [2] -> null
indexes:  0       1       2      3      4      5

Dry Run Walkthrough

Input: list: [-1, 0, 1, 2, -1, -4]

Goal: Find all unique triplets that sum to zero

Step 1: Sort the list to make it easier to find triplets

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

Why: Sorting helps us use two pointers to find pairs that sum to a target efficiently

Step 2: Fix first number at index 0 (-4), set left=1, right=5

[-4, -1, -1, 0, 1, 2] ↑fixed at -4, left=1, right=5

Why: We try to find two numbers that sum to 4 (0 - (-4))

Step 3: Sum = -4 + (-1) + 2 = -3, less than 0, move left pointer right

[-4, -1, -1, 0, 1, 2] fixed=-4, left=2, right=5

Why: Sum too small, increase left to get larger sum

Step 4: Sum = -4 + (-1) + 2 = -3, still less than 0, move left pointer right

[-4, -1, -1, 0, 1, 2] fixed=-4, left=3, right=5

Why: Sum still too small, move left pointer again

Step 5: Sum = -4 + 0 + 2 = -2, less than 0, move left pointer right

[-4, -1, -1, 0, 1, 2] fixed=-4, left=4, right=5

Why: Sum still less than zero, move left pointer

Step 6: Sum = -4 + 1 + 2 = -1, less than 0, move left pointer right

[-4, -1, -1, 0, 1, 2] fixed=-4, left=5, right=5

Why: Left and right pointers meet, no triplet with fixed -4

Step 7: Fix first number at index 1 (-1), set left=2, right=5

[-4, -1, -1, 0, 1, 2] ↑fixed at -1, left=2, right=5

Why: Try to find two numbers that sum to 1 (0 - (-1))

Step 8: Sum = -1 + (-1) + 2 = 0, found triplet [-1, -1, 2], move left and right pointers

[-4, -1, -1, 0, 1, 2] triplets=[[-1,-1,2]], left=3, right=4

Why: Sum zero means valid triplet, move pointers to find more

Step 9: Sum = -1 + 0 + 1 = 0, found triplet [-1, 0, 1], move left and right pointers

[-4, -1, -1, 0, 1, 2] triplets=[[-1,-1,2],[-1,0,1]], left=4, right=3

Why: Sum zero again, but pointers crossed, stop for this fixed

Step 10: Fix first number at index 2 (-1), skip because same as previous fixed to avoid duplicates

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

Why: Avoid duplicate triplets by skipping same fixed number

Step 11: Fix first number at index 3 (0), set left=4, right=5

[-4, -1, -1, 0, 1, 2] ↑fixed at 0, left=4, right=5

Why: Try to find two numbers that sum to 0 (0 - 0)

Step 12: Sum = 0 + 1 + 2 = 3, greater than 0, move right pointer left

[-4, -1, -1, 0, 1, 2] fixed=0, left=4, right=4

Why: Sum too big, decrease right pointer

Step 13: Left and right pointers meet, stop for fixed 0

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

Why: No more pairs to check

Step 14: Fix first number at index 4 (1), stop because left pointer would be right pointer

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

Why: No enough elements left for triplet

Result:

Triplets found: [-1, -1, 2] -> [-1, 0, 1]

Annotated Code

DSA Javascript

class Solution {
  threeSum(nums) {
    nums.sort((a, b) => a - b); // sort array
    const triplets = [];
    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) {
          triplets.push([nums[i], nums[left], nums[right]]); // found triplet
          left++;
          right--;
          while (left < right && nums[left] === nums[left - 1]) left++; // skip duplicates
          while (left < right && nums[right] === nums[right + 1]) right--; // skip duplicates
        } else if (sum < 0) {
          left++; // need bigger sum
        } else {
          right--; // need smaller sum
        }
      }
    }
    return triplets;
  }
}

// Driver code
const solution = new Solution();
const input = [-1, 0, 1, 2, -1, -4];
const result = solution.threeSum(input);
for (const triplet of result) {
  console.log(triplet.join(", ") + "\n");
}

nums.sort((a, b) => a - b); // sort array

sort input to enable two-pointer technique

if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicates

skip duplicate fixed elements to avoid repeated triplets

while (left < right) {

iterate with two pointers to find pairs summing to target

const sum = nums[i] + nums[left] + nums[right];

calculate current triplet sum

if (sum === 0) { triplets.push([nums[i], nums[left], nums[right]]); left++; right--;

found valid triplet, add and move pointers

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

skip duplicates on left pointer

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

skip duplicates on right pointer

} else if (sum < 0) { left++; } else { right--; }

adjust pointers based on sum comparison

Output

-1, -1, 2

-1, 0, 1

Complexity Analysis

Time: O(n^2) because we sort once O(n log n) and then use two nested loops with two pointers to find triplets

Space: O(k) where k is number of triplets found, for storing results

vs Alternative: Naive approach is O(n^3) by checking all triplets; this method is faster by sorting and using two pointers

Edge Cases

empty list

returns empty list, no triplets found

DSA Javascript

for (let i = 0; i < nums.length - 2; i++) {

list with less than 3 elements

returns empty list, no triplets possible

DSA Javascript

for (let i = 0; i < nums.length - 2; i++) {

list with all zeros

returns one triplet [0, 0, 0] only once

DSA Javascript

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

When to Use This Pattern

When you need to find triplets that sum to a target and avoid duplicates, use sorting plus two pointers to efficiently find unique triplets.

Common Mistakes

Mistake: Not sorting the array before applying two pointers
Fix: Sort the array first to enable two-pointer technique

Mistake: Not skipping duplicates for fixed, left, or right pointers
Fix: Add checks to skip duplicate elements to avoid repeated triplets

Mistake: Moving pointers incorrectly when sum equals zero
Fix: Move both left and right pointers after finding a valid triplet

Summary

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

Use when you need to find combinations of three numbers summing to a target efficiently.

Sort the array and use two pointers to find pairs for each fixed element while skipping duplicates.

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