Three Sum Problem All Unique Triplets in DSA Typescript - Execution Trace

Concept Flow - Three Sum Problem All Unique Triplets

Sort the array

↓

Start outer loop i from 0 to n-3

↓

Skip duplicates for i

↓

Set left = i+1, right = end

↓

While left < right

↓

Calculate sum = nums[i

↓

Add triplet

↓

Skip duplicates left/right

↓

left++

↓

right--

↓

Continue loop

↓

Repeat for next i

↓

Return all unique triplets

Sort the array, then for each element use two pointers to find pairs that sum to zero with it, skipping duplicates to ensure unique triplets.

Execution Sample

DSA Typescript

function threeSum(nums: number[]): number[][] {
  nums.sort((a,b) => a-b);
  const res: 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) {
        res.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 res;
}

This code finds all unique triplets in the array that sum to zero by sorting and using two pointers.

Execution Table

Step	Operation	i	left	right	Sum	Triplet Added	Pointer Changes	Array State
1	Sort array	-	-	-	-	No	-	[-4, -1, -1, 0, 1, 2]
2	Start outer loop	0	1	5	-	No	-	[-4, -1, -1, 0, 1, 2]
3	Calculate sum	0	1	5	-4 + (-1) + 2 = -3	No	sum < 0, left++	[-4, -1, -1, 0, 1, 2]
4	Calculate sum	0	2	5	-4 + (-1) + 2 = -3	No	sum < 0, left++	[-4, -1, -1, 0, 1, 2]
5	Calculate sum	0	3	5	-4 + 0 + 2 = -2	No	sum < 0, left++	[-4, -1, -1, 0, 1, 2]
6	Calculate sum	0	4	5	-4 + 1 + 2 = -1	No	sum < 0, left++	[-4, -1, -1, 0, 1, 2]
7	left == right, end inner loop	0	5	5	-	No	-	[-4, -1, -1, 0, 1, 2]
8	Increment i	1	2	5	-	No	-	[-4, -1, -1, 0, 1, 2]
9	Calculate sum	1	2	5	-1 + (-1) + 2 = 0	Yes	Add triplet [-1,-1,2], skip duplicates, left++, right--	[-4, -1, -1, 0, 1, 2]
10	Calculate sum	1	3	4	-1 + 0 + 1 = 0	Yes	Add triplet [-1,0,1], skip duplicates, left++, right--	[-4, -1, -1, 0, 1, 2]
11	left >= right, end inner loop	1	4	3	-	No	-	[-4, -1, -1, 0, 1, 2]
12	Increment i	2	-	-	-	No	Skip i=2 because nums[2] == nums[1]	[-4, -1, -1, 0, 1, 2]
13	Increment i	3	4	5	-	No	-	[-4, -1, -1, 0, 1, 2]
14	Calculate sum	3	4	5	0 + 1 + 2 = 3	No	sum > 0, right--	[-4, -1, -1, 0, 1, 2]
15	left >= right, end inner loop	3	4	4	-	No	-	[-4, -1, -1, 0, 1, 2]
16	Increment i	4	-	-	-	No	i=4 stops outer loop (length-2)	[-4, -1, -1, 0, 1, 2]
17	Return result	-	-	-	-	Yes	-	[[-1,-1,2], [-1,0,1]]

💡 Outer loop ends when i reaches length-2; all unique triplets found.

Variable Tracker

Variable	Start	After Step 2	After Step 9	After Step 10	After Step 13	Final
i	-	0	1	1	3	4
left	-	1	2	3	4	-
right	-	5	5	4	5	-
Triplets Found	[]	[]	[[-1,-1,2]]	[[-1,-1,2],[-1,0,1]]	[[-1,-1,2],[-1,0,1]]	[[-1,-1,2],[-1,0,1]]
Array	[-1,0,1,2,-1,-4]	[-4,-1,-1,0,1,2]	[-4,-1,-1,0,1,2]	[-4,-1,-1,0,1,2]	[-4,-1,-1,0,1,2]	[-4,-1,-1,0,1,2]

Key Moments - 3 Insights

Why do we skip duplicates for i and pointers left/right?

Skipping duplicates prevents adding the same triplet multiple times. For example, at step 12, i=2 is skipped because nums[2] equals nums[1], avoiding repeated triplets as shown in execution_table rows 9 and 10.

Why do we move left pointer when sum < 0 and right pointer when sum > 0?

Because the array is sorted, if sum is less than zero, increasing left moves to a bigger number to increase sum (steps 3-6). If sum is greater than zero, decreasing right moves to a smaller number to reduce sum (step 14).

Why does the inner loop stop when left >= right?

When left meets or passes right, all pairs for current i are checked. For example, at step 7 and 15, the inner loop ends because no more pairs remain to check.

Visual Quiz - 3 Questions

Look at the execution_table at step 9. What triplet is added to the result?

A [-1, -1, 2]

B [-4, -1, 2]

C [-1, 0, 1]

D [0, 1, 2]

💡 Hint

Check the 'Triplet Added' column at step 9 in the execution_table.

At which step does the outer loop skip an index due to duplicate value?

A Step 12

B Step 7

C Step 14

D Step 16

💡 Hint

Look for 'Skip i=2 because nums[2] == nums[1]' in the Pointer Changes column.

If the array was not sorted, which pointer movement logic would break?

A Skipping duplicates for i

B Moving left pointer when sum < 0

C Adding triplets when sum == 0

D Incrementing i in outer loop

💡 Hint

Refer to key_moments about why left/right pointers move based on sum and sorted array.

Concept Snapshot

Three Sum Problem:
- Sort array first
- For each i, use two pointers left=i+1 and right=end
- Calculate sum = nums[i]+nums[left]+nums[right]
- If sum==0, add triplet and skip duplicates
- If sum<0, move left++ to increase sum
- If sum>0, move right-- to decrease sum
- Continue until all unique triplets found

Full Transcript

The Three Sum Problem finds all unique triplets in an array that sum to zero. First, the array is sorted to allow two-pointer technique. For each element i, two pointers left and right scan the rest of the array. The sum of nums[i], nums[left], and nums[right] is checked. If zero, the triplet is added and duplicates are skipped. If sum is less than zero, left pointer moves right to increase sum. If sum is greater than zero, right pointer moves left to decrease sum. This continues until all unique triplets are found. The process stops when i reaches length-2. Skipping duplicates ensures no repeated triplets. The execution table shows step-by-step how pointers move and triplets are added.

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