Three Sum Problem All Unique Triplets in DSA Typescript

Mental Model

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

Analogy: Imagine you have a group of friends with different amounts of money. You want to find three friends whose total money adds up to zero, like balancing a small group budget exactly.

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

We pick one number, then look for two others that sum to the negative of it.
Pointers:
  i ↑
  left ->
  right ->

Dry Run Walkthrough

Input: nums = [-1, 0, 1, 2, -1, -4]

Goal: Find all unique triplets that sum to zero

Step 1: Sort the array to [-4, -1, -1, 0, 1, 2]

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

Why: Sorting helps find pairs with two pointers and avoid duplicates

Step 2: Set i=0 (value -4), set left=1, right=5

i=0(-4), left=1(-1), right=5(2)

Why: Start with first number and try to find two others summing to 4

Step 3: Sum = -4 + (-1) + 2 = -3 < 0, move left to 2

i=0(-4), left=2(-1), right=5(2)

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

Step 4: Sum = -4 + (-1) + 2 = -3 < 0, move left to 3

i=0(-4), left=3(0), right=5(2)

Why: Sum still too small, move left pointer

Step 5: Sum = -4 + 0 + 2 = -2 < 0, move left to 4

i=0(-4), left=4(1), right=5(2)

Why: Sum still less than zero, move left pointer

Step 6: Sum = -4 + 1 + 2 = -1 < 0, move left to 5

i=0(-4), left=5(2), right=5(2)

Why: Left meets right, no triplet with i=0

Step 7: Increment i to 1 (value -1), left=2, right=5

i=1(-1), left=2(-1), right=5(2)

Why: Try next number as first element

Step 8: Sum = -1 + (-1) + 2 = 0, found triplet [-1, -1, 2], add to result

result = [[-1, -1, 2]]

Why: Sum zero means valid triplet

Step 9: Move left to 3 and right to 4 to avoid duplicates

i=1(-1), left=3(0), right=4(1)

Why: Look for other pairs with i=1

Step 10: Sum = -1 + 0 + 1 = 0, found triplet [-1, 0, 1], add to result

result = [[-1, -1, 2], [-1, 0, 1]]

Why: Another valid triplet found

Step 11: Move left to 4 and right to 3, pointers cross, increment i

i=2(-1), left=3(0), right=4(1)

Why: No more pairs for i=1, move to next i

Step 12: Skip i=2 because nums[2] == nums[1] to avoid duplicates

i=3(0), left=4(1), right=5(2)

Why: Avoid duplicate triplets starting with same number

Step 13: Sum = 0 + 1 + 2 = 3 > 0, move right to 4

i=3(0), left=4(1), right=4(1)

Why: Sum too big, decrease right pointer

Step 14: Left meets right, no more triplets

End

Why: All triplets found

Result:

[-1, -1, 2] -> [-1, 0, 1] -> null

Annotated Code

DSA Typescript

class Solution {
  threeSum(nums: number[]): number[][] {
    nums.sort((a, b) => a - b) // sort array
    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]]) // found triplet
          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++ // sum too small, increase left
        } else {
          right-- // sum too big, decrease right
        }
      }
    }
    return result
  }
}

// Driver code
const solution = new Solution()
const input = [-1, 0, 1, 2, -1, -4]
const output = solution.threeSum(input)
for (const triplet of output) {
  console.log(triplet.join(', '))
}

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

sort array to enable two-pointer technique and duplicate skipping

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

skip repeated first elements to avoid duplicate 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) { result.push([nums[i], nums[left], nums[right]])

found valid triplet, add to result

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

left++

move left pointer forward after adding triplet

right--

move right pointer backward after adding triplet

else if (sum < 0) { left++ }

sum too small, increase left pointer to get bigger sum

else { right-- }

sum too big, decrease right pointer to get smaller sum

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 pointers inside a loop O(n^2)

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; two-pointer reduces to O(n^2)

Edge Cases

Empty array

Returns empty list, no triplets

DSA Typescript

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

Array with less than 3 elements

Returns empty list, no triplets possible

DSA Typescript

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

All zeros [0,0,0,0]

Returns one triplet [0,0,0] without duplicates

DSA Typescript

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

No triplets sum to zero

Returns empty list

DSA Typescript

result.push([nums[i], nums[left], nums[right]])

When to Use This Pattern

When asked to find triplets summing to zero or a target with unique sets, use sorting plus two-pointer scanning to efficiently find all solutions.

Common Mistakes

Mistake: Not sorting the array before two-pointer approach
Fix: Sort the array first to enable two-pointer scanning and duplicate skipping

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

Mistake: Moving pointers incorrectly after finding a triplet
Fix: After adding a triplet, move both pointers and skip duplicates before continuing

Summary

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

Use when you need to find combinations of three numbers summing to zero without duplicates.

Sort the array and use two pointers to efficiently find pairs complementing the current number.

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