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

Concept Flow - Three Sum Problem All Unique Triplets

Sort the array

↓

Fix first element i

↓

Set left = i+1, right = end

↓

While left < right

↓

Sum == 0?

↓

Add triplet

↓

Skip duplicates

↓

Move left and right pointers

↓

Repeat until left >= right

↓

Move i to next unique element

↓

Repeat until i reaches end

↓

Return all unique triplets

We sort the array, then fix one element and use two pointers to find pairs that sum to zero with it, skipping duplicates to get unique triplets.

Execution Sample

DSA Go

nums := []int{-1, 0, 1, 2, -1, -4}
sort.Ints(nums)
for i := 0; i < len(nums)-2; i++ {
  left, right := i+1, len(nums)-1
  // find pairs with nums[i]
}

Sort the array and use a loop with two pointers to find all unique triplets that sum to zero.

Execution Table

Step	Operation	i (fixed)	left	right	Sum	Triplets Found	Pointer Moves	Array State
1	Sort array	-	-	-	-	[]	-	[-4, -1, -1, 0, 1, 2]
2	Fix i=0	0 (-4)	1	5	-4 + (-1) + 2 = -3	[]	left++	[-4, -1, -1, 0, 1, 2]
3	Check sum	0 (-4)	2	5	-4 + (-1) + 2 = -3	[]	left++	[-4, -1, -1, 0, 1, 2]
4	Check sum	0 (-4)	3	5	-4 + 0 + 2 = -2	[]	left++	[-4, -1, -1, 0, 1, 2]
5	Check sum	0 (-4)	4	5	-4 + 1 + 2 = -1	[]	left++	[-4, -1, -1, 0, 1, 2]
6	left >= right	0 (-4)	-	-	-	[]	Move i to next	[-4, -1, -1, 0, 1, 2]
7	Fix i=1	1 (-1)	2	5	-1 + (-1) + 2 = 0	[[-1, -1, 2]]	left++, right--	[-4, -1, -1, 0, 1, 2]
8	Skip duplicate left	1 (-1)	3	4	-1 + 0 + 1 = 0	[[-1, -1, 2], [-1, 0, 1]]	left++, right--	[-4, -1, -1, 0, 1, 2]
9	left >= right	1 (-1)	-	-	-	[[-1, -1, 2], [-1, 0, 1]]	Move i to next unique	[-4, -1, -1, 0, 1, 2]
10	Fix i=2 (skip duplicate -1)	2 (-1)	-	-	-	[[-1, -1, 2], [-1, 0, 1]]	Skip i	[-4, -1, -1, 0, 1, 2]
11	Fix i=3	3 (0)	4	5	0 + 1 + 2 = 3	[[-1, -1, 2], [-1, 0, 1]]	right--	[-4, -1, -1, 0, 1, 2]
12	left >= right	3 (0)	-	-	-	[[-1, -1, 2], [-1, 0, 1]]	Move i to next	[-4, -1, -1, 0, 1, 2]
13	Fix i=4	4 (1)	-	-	-	[[-1, -1, 2], [-1, 0, 1]]	Stop (less than 3 elements left)	[-4, -1, -1, 0, 1, 2]

💡 i reaches 4, less than 3 elements remain to form triplet, stop.

Variable Tracker

Variable	Start	After Step 2	After Step 7	After Step 8	After Step 11	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]]

Key Moments - 3 Insights

Why do we skip duplicate elements for i and left pointers?

Skipping duplicates prevents adding the same triplet multiple times. For example, at step 10, i=2 is a duplicate of i=1, so we skip it to avoid 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 < 0, increasing left moves to a bigger number to increase sum (steps 2-5). If sum > 0, decreasing right moves to a smaller number to reduce sum (step 11). This is shown in pointer moves in execution_table.

Why stop when i reaches len(nums)-2?

We need at least three numbers to form a triplet. When i reaches len(nums)-2, fewer than 3 elements remain, so no more triplets can form (exit at step 13).

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what triplet is found?

A [-1, -1, 2]

B [-1, 0, 1]

C [0, 1, 2]

D [-4, 1, 2]

💡 Hint

Check the 'Triplets Found' column at step 7 in execution_table.

At which step does the left pointer move past duplicates to avoid repeated triplets?

A Step 3

B Step 8

C Step 11

D Step 10

💡 Hint

Look at pointer moves and triplets found at step 8 in execution_table.

If the array was not sorted, which part of the execution_table would be invalid?

A Pointer moves based on sum comparison

B Triplets found at step 7

C Skipping duplicates for i

D Final exit condition at step 13

💡 Hint

Pointer moves rely on sorted array to decide left++ or right-- as shown in execution_table steps 2-5 and 11.

Concept Snapshot

Three Sum Problem:
- Sort array first
- Fix one element i
- Use two pointers left=i+1, right=end
- Move pointers based on sum:
  sum == 0: record triplet, move both skipping duplicates
  sum < 0: move left++
  sum > 0: move right--
- Skip duplicates for i and pointers
- Stop when less than 3 elements remain

Full Transcript

The Three Sum problem finds all unique triplets in an array that sum to zero. We start by sorting the array to make it easier to find pairs. Then, we fix one element at a time and use two pointers to find pairs that sum with the fixed element to zero. We move pointers based on the sum: if sum is less than zero, we move the left pointer right to increase sum; if sum is greater than zero, we move the right pointer left to decrease sum. When sum equals zero, we record the triplet and move both pointers, skipping duplicates to avoid repeated triplets. We repeat this until all elements are processed or fewer than three elements remain. This approach ensures all unique triplets are found efficiently.

Practice

1. What is the main goal of the Three Sum Problem All Unique Triplets in data structures and algorithms?

easy

A. Count the number of pairs that sum to a target

B. Find all unique triplets in an array that sum to zero

C. Find the maximum element in the array

D. Sort the array in ascending order

Solution

1. Step 1: Understand the problem statement

   The problem asks to find all unique groups of three numbers in an array whose sum is zero.

2. Step 2: Identify the goal

   The goal is to find triplets (three numbers) that add up to zero without duplicates.

3. Final Answer:

   Find all unique triplets in an array 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 to zero without repeats [OK]

Common Mistakes:

• Confusing with pair sum problems
• Ignoring uniqueness of triplets
• Trying to find max or min instead of sum

2. Which of the following Go code snippets correctly initializes a slice of integers for solving the Three Sum problem?

easy

A. nums := []int{1, -1, 0, 2, -2}

B. nums := [1, -1, 0, 2, -2]

C. nums := (1, -1, 0, 2, -2)

D. nums := {1, -1, 0, 2, -2}

Solution

1. Step 1: Recall Go slice initialization syntax

   In Go, slices are initialized with square brackets and type, e.g., []int{...}.

2. Step 2: Check each option

   nums := []int{1, -1, 0, 2, -2} uses correct syntax: nums := []int{1, -1, 0, 2, -2}. Others use invalid syntax.

3. Final Answer:

   nums := []int{1, -1, 0, 2, -2} -> Option A

4. Quick Check:

   Go slice syntax = []int{...} [OK]

Hint: Use []int{...} to declare integer slices in Go [OK]

Common Mistakes:

• Using parentheses or braces instead of curly braces
• Missing type declaration []int
• Using array literal syntax without type

3. What will be the output of the following Go code snippet that finds unique triplets summing to zero?

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    var res [][]int
    for i := 0; i < len(nums)-2; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        left, right := i+1, len(nums)-1
        for left < right {
            sum := nums[i] + nums[left] + nums[right]
            if sum == 0 {
                res = append(res, []int{nums[i], nums[left], nums[right]})
                for left < right && nums[left] == nums[left+1] {
                    left++
                }
                for left < right && nums[right] == nums[right-1] {
                    right--
                }
                left++
                right--
            } else if sum < 0 {
                left++
            } else {
                right--
            }
        }
    }
    return res
}

fmt.Println(threeSum([]int{-1, 0, 1, 2, -1, -4}))

medium

A. [[-4, 2, 2], [-1, 0, 1]]

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

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

D. [[-1, 1, 1], [0, 0, 0]]

Solution

1. Step 1: Sort and iterate through the array

   The sorted array is [-4, -1, -1, 0, 1, 2]. The code skips duplicates and uses two pointers to find triplets summing to zero.

2. Step 2: Identify unique triplets summing to zero

   Triplets found are [-1, -1, 2] and [-1, 0, 1]. These are appended to the result.

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 zero sum triplets [OK]

Common Mistakes:

• Not sorting array before processing
• Not skipping duplicates causing repeated triplets
• Incorrect pointer movement logic

4. Identify the bug in the following Go code snippet for the Three Sum problem:

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    var res [][]int
    for i := 0; i < len(nums)-2; i++ {
        left, right := i+1, len(nums)-1
        for left < right {
            sum := nums[i] + nums[left] + nums[right]
            if sum == 0 {
                res = append(res, []int{nums[i], nums[left], nums[right]})
                left++
                right--
            } else if sum < 0 {
                left++
            } else {
                right--
            }
        }
    }
    return res
}

medium

A. Returning res before the loop ends

B. Incorrect initialization of left and right pointers

C. Using sort.Ints instead of sort.Sort

D. Missing check to skip duplicate elements for i, left, and right

Solution

1. Step 1: Analyze duplicate handling

   The code does not skip duplicate values for i, left, or right, which can cause duplicate triplets in the result.

2. Step 2: Confirm other parts are correct

   Initialization of pointers and sorting are correct. The return statement is after loops, so no premature return.

3. Final Answer:

   Missing check to skip duplicate elements for i, left, and right -> Option D

4. Quick Check:

   Skipping duplicates is essential to avoid repeated triplets [OK]

Hint: Always skip duplicates to ensure unique triplets [OK]

Common Mistakes:

• Not skipping duplicates causing repeated triplets
• Incorrect pointer updates after finding a triplet
• Sorting with wrong function

5. Given the input array nums := []int{-2, 0, 1, 2, -1, -1, 3}, which of the following is the correct set of all unique triplets that sum to zero?

hard

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

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

C. [[-2, -1, 3], [-1, 0, 1], [1, 1, -2]]

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

Solution

1. Step 1: Sort the array and find triplets

   Sorted array: [-2, -1, -1, 0, 1, 2, 3]. Find unique triplets summing to zero by two-pointer method.

2. Step 2: Identify all unique triplets

   Triplets are [-2, -1, 3], [-2, 0, 2], [-1, -1, 2], and [-1, 0, 1]. These cover all unique zero sums.

3. Final Answer:

   [[-2, -1, 3], [-2, 0, 2], [-1, -1, 2], [-1, 0, 1]] -> Option A

4. Quick Check:

   All unique triplets summing zero = [[-2, -1, 3], [-2, 0, 2], [-1, -1, 2], [-1, 0, 1]] [OK]

Hint: Sort array, then find triplets with two pointers skipping duplicates [OK]

Common Mistakes:

• Missing some triplets due to not skipping duplicates
• Including triplets with repeated elements incorrectly
• Not sorting array before processing