Three Sum Problem All Unique Triplets in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Three Sum Unique Triplets Function

What is the output of the following TypeScript function when called with the input [-1, 0, 1, 2, -1, -4]?

DSA Typescript

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;
    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;
}

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

A [[-1, 0, 1], [0, 1, -1]]

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

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

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

💡 Hint

Remember the function sorts the array and skips duplicates to find unique triplets that sum to zero.

The function sorts the input array and uses a two-pointer approach to find all unique triplets that sum to zero. It skips duplicates to avoid repeated triplets. For the input [-1, 0, 1, 2, -1, -4], the unique triplets are [-1, -1, 2] and [-1, 0, 1].

🧠 Conceptual

intermediate

Understanding the Role of Sorting in Three Sum

Why is sorting the input array important in the Three Sum problem solution?

A It allows skipping duplicates easily and enables the two-pointer technique to find pairs efficiently.

B It changes the original array to a new array with only positive numbers.

C It is required to convert the array into a linked list for traversal.

D It helps to find the maximum number in the array quickly.

💡 Hint

Think about how duplicates and pair searching are handled.

Sorting helps to skip duplicate elements easily by comparing adjacent elements. It also allows the use of the two-pointer technique to find pairs that sum to a target efficiently, reducing the time complexity.

🔧 Debug

advanced

Identify the Error in the Three Sum Implementation

What error will the following code produce when run with input [-2, 0, 1, 1, 2]?

DSA Typescript

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

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

A TypeError because nums[i - 1] is undefined when i = 0

B No error, outputs [[-2, 0, 2], [-2, 1, 1]]

C SyntaxError due to missing semicolon

D Runtime error due to infinite loop

💡 Hint

Check the condition that skips duplicates carefully.

The condition if (nums[i] === nums[i - 1]) continue; causes a TypeError when i = 0 because nums[-1] is undefined. The correct check should be if (i > 0 && nums[i] === nums[i - 1]) continue; to avoid accessing out-of-bound index.

❓ Predict Output

advanced

Output of Three Sum with No Valid Triplets

What is the output of the threeSum function when called with input [1, 2, -2, -1]?

DSA Typescript

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;
    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;
}

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

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

B [[1, 2, -3]]

C [[1, -1, 0]]

D []

💡 Hint

Check if any three numbers sum to zero in the sorted array.

No three numbers in the input array sum to zero, so the function returns an empty array.

🚀 Application

expert

Count Unique Triplets Summing to Zero

Given the function threeSum that returns all unique triplets summing to zero, what is the count of unique triplets for the input [-3, 0, 1, 2, -1, 1, -2]?

DSA Typescript

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;
    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;
}

const triplets = threeSum([-3, 0, 1, 2, -1, 1, -2]);
console.log(triplets.length);

A 5

B 4

C 3

D 6

💡 Hint

List all unique triplets manually after sorting the array.

The unique triplets summing to zero are [-3, 1, 2], [-2, 0, 2], and [-1, 0, 1]. There are 3 such triplets.

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