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

Concept Flow - Three Sum Problem All Unique Triplets

Sort the array

↓

For each element i

↓

Set left = i+1, right = end

↓

While left < right

↓

Sum = arr[i

↓

Sum == 0?

Yes→Add triplet

↓

Sum < 0?

Yes→left++

No |↓

right--

↓

Skip duplicates

↓

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 Javascript

function threeSum(nums) {
  nums.sort((a,b) => a-b);
  const res = [];
  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(nums[left]===nums[left+1]) left++;
        while(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	Action	Triplets Found	Array State
1	Sort array	-	-	-	-	-	[]	[-4, -1, -1, 0, 1, 2]
2	Start i loop	0	-	-	-	Check duplicates (none)	[]	[-4, -1, -1, 0, 1, 2]
3	Set pointers	0	1	5	-	-	[]	[-4, -1, -1, 0, 1, 2]
4	Calculate sum	0	1	5	-4 + (-1) + 2 = -3	Sum < 0, left++	[]	[-4, -1, -1, 0, 1, 2]
5	Update pointers	0	2	5	-	-	[]	[-4, -1, -1, 0, 1, 2]
6	Calculate sum	0	2	5	-4 + (-1) + 2 = -3	Sum < 0, left++	[]	[-4, -1, -1, 0, 1, 2]
7	Update pointers	0	3	5	-	-	[]	[-4, -1, -1, 0, 1, 2]
8	Calculate sum	0	3	5	-4 + 0 + 2 = -2	Sum < 0, left++	[]	[-4, -1, -1, 0, 1, 2]
9	Update pointers	0	4	5	-	-	[]	[-4, -1, -1, 0, 1, 2]
10	Calculate sum	0	4	5	-4 + 1 + 2 = -1	Sum < 0, left++	[]	[-4, -1, -1, 0, 1, 2]
11	Update pointers	0	5	5	-	-	[]	[-4, -1, -1, 0, 1, 2]
12	While ends	0	5	5	-	left not < right, end while	[]	[-4, -1, -1, 0, 1, 2]
13	Next i	1	-	-	-	Check duplicates (i=1, nums[1]=-1, nums[0]=-4 different)	[]	[-4, -1, -1, 0, 1, 2]
14	Set pointers	1	2	5	-	-	[]	[-4, -1, -1, 0, 1, 2]
15	Calculate sum	1	2	5	-1 + (-1) + 2 = 0	Sum == 0, add triplet	[[-1, -1, 2]]	[-4, -1, -1, 0, 1, 2]
16	Skip duplicates left	1	2	5	-	nums[2] == nums[3]? No	-	[-4, -1, -1, 0, 1, 2]
17	Skip duplicates right	1	2	5	-	nums[5] == nums[4]? No	-	[-4, -1, -1, 0, 1, 2]
18	Move pointers	1	3	4	-	-	[[-1, -1, 2]]	[-4, -1, -1, 0, 1, 2]
19	Calculate sum	1	3	4	-1 + 0 + 1 = 0	Sum == 0, add triplet	[[-1, -1, 2], [-1, 0, 1]]	[-4, -1, -1, 0, 1, 2]
20	Skip duplicates left	1	3	4	-	nums[3] == nums[4]? No	-	[-4, -1, -1, 0, 1, 2]
21	Skip duplicates right	1	3	4	-	nums[4] == nums[3]? No	-	[-4, -1, -1, 0, 1, 2]
22	Move pointers	1	4	3	-	-	[[-1, -1, 2], [-1, 0, 1]]	[-4, -1, -1, 0, 1, 2]
23	While ends	1	4	3	-	left not < right, end while	[[-1, -1, 2], [-1, 0, 1]]	[-4, -1, -1, 0, 1, 2]
24	Next i	2	-	-	-	Check duplicates (nums[2] == nums[1], skip i=2)	[[-1, -1, 2], [-1, 0, 1]]	[-4, -1, -1, 0, 1, 2]
25	Next i	3	-	-	-	Check duplicates (nums[3]=0, nums[2]=-1 different)	[[-1, -1, 2], [-1, 0, 1]]	[-4, -1, -1, 0, 1, 2]
26	Set pointers	3	4	5	-	-	[[-1, -1, 2], [-1, 0, 1]]	[-4, -1, -1, 0, 1, 2]
27	Calculate sum	3	4	5	0 + 1 + 2 = 3	Sum > 0, right--	[[-1, -1, 2], [-1, 0, 1]]	[-4, -1, -1, 0, 1, 2]
28	Update pointers	3	4	4	-	-	[[-1, -1, 2], [-1, 0, 1]]	[-4, -1, -1, 0, 1, 2]
29	While ends	3	4	4	-	left not < right, end while	[[-1, -1, 2], [-1, 0, 1]]	[-4, -1, -1, 0, 1, 2]
30	Next i	4	-	-	-	i=4 stops loop (length-2=4)	[[-1, -1, 2], [-1, 0, 1]]	[-4, -1, -1, 0, 1, 2]
31	Return result	-	-	-	-	Return all unique triplets	[[-1, -1, 2], [-1, 0, 1]]	[-4, -1, -1, 0, 1, 2]

💡 i reaches length-2, no more triplets possible, return result

Variable Tracker

Variable	Start	After i=0	After i=1	After i=3	Final
i	-	0	1	3	4 (loop ends)
left	-	1 to 5 (incremented)	2 to 4 (incremented and decremented)	4 to 4	-
right	-	5 to 5 (decremented)	5 to 3	5 to 4	-
Triplets Found	[]	[]	[[-1,-1,2],[-1,0,1]]	[[-1,-1,2],[-1,0,1]]	[[-1,-1,2],[-1,0,1]]
Array State	[-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?

Skipping duplicates avoids adding the same triplet multiple times. For example, at step 24, i=2 is skipped because nums[2] equals nums[1], preventing duplicate triplets.

Why do we move left pointer when sum < 0?

Because the array is sorted, increasing left moves to a bigger number, increasing sum. At step 4, sum was -3, so left++ tries to increase sum towards zero.

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

Because left and right pointers cross, meaning all pairs for current i are checked. At step 12 and 23, left is not less than right, so loop ends.

Visual Quiz - 3 Questions

Look at the execution table at step 15. What triplet is added to the result?

A [-4, -1, 2]

B [-1, -1, 2]

C [-1, 0, 1]

D [0, 1, 2]

💡 Hint

Check the 'Triplets Found' column at step 15 in the execution table.

At which step does the condition left < right become false for i=1?

A Step 29

B Step 12

C Step 23

D Step 31

💡 Hint

Look at the 'Action' column for i=1 where the while loop ends.

If the array had no duplicates, how would the execution table change?

A No steps would skip duplicates, so more triplets might be added.

B The array would not be sorted.

C The pointers would not move.

D The loop would run infinitely.

💡 Hint

Refer to steps 16, 17, and 24 where duplicates are skipped.

Concept Snapshot

Three Sum Problem:
- Sort array first
- For each element 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 pointer right
- If sum>0, move right pointer left
- Continue until left >= right
- Return all unique triplets

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 to the result and duplicates are skipped by moving pointers past equal values. 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 left pointer is no longer less than right pointer. The process repeats for each i, skipping duplicate values to avoid repeated triplets. Finally, all unique triplets are returned.

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