Three Sum Problem All Unique Triplets in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the goal of the Three Sum Problem?

To find all unique triplets in an array that add up to zero.

beginner

Why do we sort the array before solving the Three Sum Problem?

Sorting helps to avoid duplicates easily and allows using two pointers to find pairs efficiently.

intermediate

Explain the two-pointer technique used in the Three Sum Problem.

After fixing one number, use two pointers starting from the next element and the end of the array to find pairs that sum to the negative of the fixed number.

intermediate

How do you avoid duplicate triplets in the Three Sum Problem?

Skip over duplicate numbers for the fixed element and also skip duplicates when moving the two pointers.

intermediate

What is the time complexity of the common Three Sum solution using sorting and two pointers?

O(n^2), where n is the number of elements in the array.

What is the first step in solving the Three Sum Problem efficiently?

A Sort the array

B Use a hash map

C Reverse the array

D Remove duplicates first

Sorting the array is the first step to help use two pointers and avoid duplicates.

In the two-pointer approach, what do the two pointers represent?

A Random positions in the array

B Start and end of the array segment after the fixed element

C The first and last elements of the whole array

D The smallest and largest elements in the array

The two pointers start just after the fixed element and at the end of the array segment to find pairs.

How do you handle duplicates for the fixed element in the Three Sum Problem?

A Use a hash set to store duplicates

B Always include duplicates

C Remove duplicates before processing

D Skip the fixed element if it is the same as the previous one

Skipping the fixed element if it is the same as the previous avoids duplicate triplets.

What is the sum target for the two pointers after fixing one element?

A Zero

B Sum of the fixed element and zero

C Negative of the fixed element

D Double the fixed element

The two pointers look for pairs that sum to the negative of the fixed element to make total zero.

What is the overall time complexity of the Three Sum solution using sorting and two pointers?

A O(n^2)

B O(n log n)

C O(n^3)

D O(n)

Sorting takes O(n log n), and the two-pointer search inside a loop takes O(n^2) total.

Describe the step-by-step approach to solve the Three Sum Problem with unique triplets.

Think about sorting first, then how to find pairs efficiently.

Explain how to avoid duplicate triplets in the Three Sum Problem solution.

Duplicates can come from fixed element or from pairs found.

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