Three Sum Problem All Unique Triplets in DSA Typescript - Time & Space Complexity

Time Complexity: Three Sum Problem All Unique Triplets

O(n²)

Understanding Time Complexity

We want to understand how the time needed to find all unique triplets that sum to zero grows as the input list gets bigger.

How does the number of steps change when we have more numbers to check?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code finds all unique triplets in the array that add up to zero by sorting and using a two-pointer approach inside a loop.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The outer loop runs through each number, and for each, the inner while loop moves two pointers to find pairs.
• How many times: The outer loop runs about n times, and the inner loop runs up to n times in total for each outer iteration.

How Execution Grows With Input

As the input size grows, the number of steps grows roughly with the square of the input size.

Input Size (n)	Approx. Operations
10	About 100
100	About 10,000
1000	About 1,000,000

Pattern observation: Doubling the input size roughly quadruples the work, showing a squared growth pattern.

Final Time Complexity

Time Complexity: O(n²)

This means the time needed grows roughly with the square of the number of elements in the input.

Common Mistake

[X] Wrong: "Because there are three numbers, the time complexity must be O(n³)."

[OK] Correct: The sorting and two-pointer method reduce the inner search to linear time, so the total work is n times n, not n times n times n.

Interview Connect

Understanding this time complexity helps you explain how to efficiently find triplets without checking every combination, a skill valued in problem solving.

Self-Check

"What if we did not sort the array first? How would the time complexity change?"

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