Three Sum Problem All Unique Triplets in DSA Go

Mental Model

Find three numbers in a list that add up to zero without repeating the same triplet.

Analogy: Imagine you have a group of friends with different ages, and you want to find three friends whose ages add up exactly to zero, but you don't want to count the same group twice.

nums: [-4, -1, 0, 1, 2, 3]
indexes:  0   1  2  3  4  5

We pick one number, then look for two others that sum to the negative of it.

Dry Run Walkthrough

Input: nums: [-1, 0, 1, 2, -1, -4]

Goal: Find all unique triplets that sum to zero

Step 1: Sort the array

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

Why: Sorting helps to avoid duplicates and use two-pointer technique

Step 2: Pick first element nums[0] = -4, set left=1, right=5

[-4, -1, -1, 0, 1, 2]
first=-4, left=-1, right=2

Why: Try to find two numbers that sum to 4 (because -4 + x + y = 0 means x + y = 4)

Step 3: Sum = -4 + (-1) + 2 = -3 < 0, move left pointer right

[-4, -1, -1, 0, 1, 2]
first=-4, left=-1, right=2

Why: Sum too small, increase left to get bigger sum

Step 4: Sum = -4 + (-1) + 2 = -3 < 0, move left pointer right

[-4, -1, -1, 0, 1, 2]
first=-4, left=0, right=2

Why: Still too small, move left pointer

Step 5: No triplet found with first = -4, move to next first element nums[1] = -1

[-4, -1, -1, 0, 1, 2]
first=-1, left=2, right=5

Why: Try new first element to find triplets

Step 6: Sum = -1 + (-1) + 2 = 0, found triplet [-1, -1, 2], move left and right to avoid duplicates

[-4, -1, -1, 0, 1, 2]
triplets: [[-1, -1, 2]]

Why: Found valid triplet, move pointers to find others

Step 7: Sum = -1 + 0 + 1 = 0, found triplet [-1, 0, 1], move left and right

[-4, -1, -1, 0, 1, 2]
triplets: [[-1, -1, 2], [-1, 0, 1]]

Why: Found another valid triplet

Step 8: Move to next first element nums[2] = -1 (skip duplicate), then nums[3] = 0

[-4, -1, -1, 0, 1, 2]
triplets: [[-1, -1, 2], [-1, 0, 1]]

Why: Avoid duplicate first elements to prevent repeated triplets

Step 9: With first=0, left=4, right=5, sum=0+1+2=3 > 0, move right pointer left

[-4, -1, -1, 0, 1, 2]
triplets: [[-1, -1, 2], [-1, 0, 1]]

Why: Sum too big, decrease right pointer

Step 10: left and right pointers cross, no more triplets with first=0

[-4, -1, -1, 0, 1, 2]
triplets: [[-1, -1, 2], [-1, 0, 1]]

Why: No more pairs to check

Result:

[-1, -1, 2] -> [-1, 0, 1]
All unique triplets found

Annotated Code

DSA Go

package main

import (
	"fmt"
	"sort"
)

func threeSum(nums []int) [][]int {
	sort.Ints(nums) // sort array to use two pointers and avoid duplicates
	result := [][]int{}
	for i := 0; i < len(nums)-2; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue // skip duplicate first elements
		}
		left, right := i+1, len(nums)-1
		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			if sum == 0 {
				result = append(result, []int{nums[i], nums[left], nums[right]})
				left++
				right--
				// skip duplicates for left
				for left < right && nums[left] == nums[left-1] {
					left++
				}
				// skip duplicates for right
				for left < right && nums[right] == nums[right+1] {
					right--
				}
			} else if sum < 0 {
				left++ // sum too small, move left pointer right
			} else {
				right-- // sum too big, move right pointer left
			}
		}
	}
	return result
}

func main() {
	nums := []int{-1, 0, 1, 2, -1, -4}
	triplets := threeSum(nums)
	for _, triplet := range triplets {
		fmt.Printf("%d -> %d -> %d -> null\n", triplet[0], triplet[1], triplet[2])
	}
}

sort.Ints(nums) // sort array to use two pointers and avoid duplicates

sort array to enable two-pointer technique and skip duplicates

if i > 0 && nums[i] == nums[i-1] { continue }

skip duplicate first elements to avoid repeated triplets

left, right := i+1, len(nums)-1

initialize two pointers to find pairs that sum with nums[i] to zero

sum := nums[i] + nums[left] + nums[right]

calculate current triplet sum

if sum == 0 { append triplet; move pointers; skip duplicates }

found valid triplet, add to result and move pointers skipping duplicates

else if sum < 0 { left++ } else { right-- }

adjust pointers to increase or decrease sum

Output

-1 -> -1 -> 2 -> null

-1 -> 0 -> 1 -> null

Complexity Analysis

Time: O(n^2) because we sort once O(n log n) and then use two nested loops with two pointers to find triplets

Space: O(k) where k is number of triplets found, plus O(n) for sorting space

vs Alternative: Naive approach is O(n^3) by checking all triplets; this method is faster by sorting and using two pointers

Edge Cases

empty array

returns empty list, no triplets found

DSA Go

for i := 0; i < len(nums)-2; i++ {

array with less than 3 elements

returns empty list, no triplets possible

DSA Go

for i := 0; i < len(nums)-2; i++ {

array with all zeros

returns one triplet [0,0,0] without duplicates

DSA Go

if sum == 0 { ... skip duplicates for left and right }

When to Use This Pattern

When asked to find triplets summing to zero or a target with unique results, use sorting plus two-pointer approach to efficiently find all unique triplets.

Common Mistakes

Mistake: Not sorting the array before two-pointer search
Fix: Sort the array first to enable two-pointer technique and duplicate skipping

Mistake: Not skipping duplicates for first, left, or right pointers
Fix: Add checks to skip duplicate elements to avoid repeated triplets

Mistake: Moving pointers incorrectly when sum equals zero
Fix: After finding a triplet, move both pointers and skip duplicates before continuing

Summary

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

Use when you need to find combinations of three numbers summing to zero without duplicates.

Sort the array and use two pointers to efficiently find triplets while skipping duplicates.

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