Three Sum Problem All Unique Triplets in DSA Go - Build from Scratch

Three Sum Problem All Unique Triplets

📖 Scenario: Imagine you are working on a financial app that analyzes a list of daily changes in stock prices. You want to find all unique sets of three days where the total change sums to zero. This helps identify balanced periods where gains and losses cancel out.

🎯 Goal: Build a Go program that finds all unique triplets in a list of integers that sum to zero. The program will output these triplets as slices of integers.

📋 What You'll Learn

Create a slice of integers named nums with the exact values: -1, 0, 1, 2, -1, -4

Create an integer variable n to store the length of nums

Implement the core logic to find all unique triplets in nums that sum to zero using sorting and two-pointer technique

Store the result in a slice of slices of integers named result

Print the result slice

💡 Why This Matters

🌍 Real World

Finding balanced triplets in financial data or sets of numbers helps in risk analysis and pattern detection.

💼 Career

This problem is common in coding interviews and tests your ability to use sorting, pointers, and handle duplicates efficiently.

1

Create the initial data slice

Create a slice of integers called nums with these exact values: -1, 0, 1, 2, -1, -4

DSA Go

nums := []int{-1, 0, 1, 2, -1, -4} // Your code here

Hint

Use nums := []int{...} to create the slice with the exact numbers.

2

Add length variable for the slice

Create an integer variable called n and set it to the length of nums using len(nums)

DSA Go

package main

func main() {
    nums := []int{-1, 0, 1, 2, -1, -4}
    n := len(nums) // Your code here
}

Hint

Use len(nums) to get the length of the slice.

3

Implement the three sum logic

Sort the nums slice using sort.Ints(nums). Then create a slice of slices of integers called result. Use a for loop with variable i from 0 to n-2. Inside, skip duplicates by checking if i > 0 and nums[i] == nums[i-1]. Use two pointers left and right initialized to i+1 and n-1. While left < right, calculate sum := nums[i] + nums[left] + nums[right]. If sum == 0, append []int{nums[i], nums[left], nums[right]} to result, then move left and right skipping duplicates. If sum < 0, increment left. Else decrement right.

DSA Go

package main

import "sort"

func main() {
    nums := []int{-1, 0, 1, 2, -1, -4}
    n := len(nums)
    sort.Ints(nums)
    var result [][]int
    // Your code here
}

Hint

Use sorting and two pointers to find triplets. Remember to skip duplicates to get unique triplets.

4

Print the result

Print the result slice using fmt.Println(result)

DSA Go

package main

import "fmt"
import "sort"

func main() {
    nums := []int{-1, 0, 1, 2, -1, -4}
    n := len(nums)
    sort.Ints(nums)
    var result [][]int

    for i := 0; i  0 && nums[i] == nums[i-1] {
            continue
        }
        left, right := i+1, n-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--
                for left < right && nums[left] == nums[left-1] {
                    left++
                }
                for left < right && nums[right] == nums[right+1] {
                    right--
                }
            } else if sum < 0 {
                left++
            } else {
                right--
            }
        }
    }
    fmt.Println(result) // Your code here
}

Hint

Use fmt.Println(result) to display the final list of triplets.

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