Three Sum Problem All Unique Triplets in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Three Sum Problem?

To find all unique triplets in an array that add up to zero.

beginner

Why do we sort the array before solving the Three Sum Problem?

Sorting helps to avoid duplicates easily and allows using two pointers to find pairs efficiently.

intermediate

Explain the two-pointer technique used in the Three Sum Problem.

After fixing one element, use two pointers starting from the next element and the end of the array to find pairs that sum to the negative of the fixed element.

intermediate

How do we ensure that the triplets are unique in the Three Sum Problem?

By skipping duplicate elements while iterating and moving pointers, we avoid adding the same triplet multiple times.

intermediate

What is the time complexity of the common solution to the Three Sum Problem?

O(n^2), where n is the number of elements in the array, due to sorting and the two-pointer search for each element.

What is the first step in solving the Three Sum Problem efficiently?

A Reverse the array

B Sort the array

C Use a hash map

D Remove duplicates first

Sorting the array is the first step to enable the two-pointer technique and easy duplicate skipping.

In the two-pointer approach, what do the two pointers represent?

A Random positions in the array

B Indices of the same element

C Start and end indices to find pairs

D Indices of duplicates

The two pointers start from the next element after the fixed one and from the end, moving inward to find pairs.

How do we avoid adding duplicate triplets to the result?

A Sort triplets after finding them

B Add all triplets and remove duplicates later

C Use a hash set of triplets

D Skip duplicate elements during iteration and pointer moves

Skipping duplicates during iteration prevents repeated triplets from being added.

What is the target sum for the two-pointer search after fixing one element?

A Negative of the fixed element

B Zero

C Sum of all elements

D Fixed element itself

We look for two numbers that sum to the negative of the fixed element to make the total zero.

What is the overall time complexity of the Three Sum solution using sorting and two pointers?

A O(n^2)

B O(n log n)

C O(n^3)

D O(n)

Sorting takes O(n log n), and the two-pointer search for each element takes O(n^2) overall.

Describe the step-by-step approach to solve the Three Sum Problem with unique triplets.

Think about sorting, fixing one element, and searching pairs with two pointers.

Explain how skipping duplicates works in the Three Sum Problem to ensure unique triplets.

Focus on how to avoid counting the same triplet multiple times.

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