Three Sum Problem All Unique Triplets in DSA Javascript - 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 ensure the triplets are unique in the Three Sum Problem?

Skip duplicate elements for the fixed number and also skip duplicates when moving the two pointers.

intermediate

What is the time complexity of the common solution to the Three Sum Problem?

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

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

A Find the maximum element

B Use a hash map

C Reverse the array

D Sort the array

Sorting the array helps to efficiently find triplets and avoid duplicates.

In the two-pointer approach, after fixing one element, where do the two pointers start?

A One just after the fixed element, one at the end

B Both at the start of the array

C Both at the end of the array

D Random positions

One pointer starts just after the fixed element, the other at the end to find pairs summing to the target.

How do you handle duplicates to ensure unique triplets?

A Ignore duplicates only for the fixed element

B Ignore duplicates for both fixed element and two pointers

C Ignore duplicates only for the two pointers

D Do not ignore duplicates

Skipping duplicates for both fixed element and pointers avoids repeated triplets.

What is the sum target for the two-pointer search after fixing one element 'x'?

A -x

B 0

C x

D x * 2

The two pointers look for pairs that sum to '-x' so the total triplet sums to zero.

What is the overall time complexity of the common Three Sum solution?

A O(n)

B O(n log n)

C O(n^2)

D O(n^3)

The solution uses sorting O(n log n) plus a nested loop with two pointers O(n^2), overall O(n^2).

Describe step-by-step how to find all unique triplets that sum to zero in an array.

Think about sorting, fixing one number, and searching pairs with two pointers.

Explain why skipping duplicates is important in the Three Sum Problem and how it is done.

Duplicates come from repeated numbers in sorted array.

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