Three Sum Problem All Unique Triplets in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Three Sum Unique Triplets Function

What is the output of the following Go function that finds all unique triplets in the array which gives the sum of zero?

DSA Go

package main
import "fmt"
func threeSum(nums []int) [][]int {
    var res [][]int
    n := len(nums)
    if n < 3 {
        return res
    }
    // Sort the array
    for i := 0; i < n-1; i++ {
        minIdx := i
        for j := i + 1; j < n; j++ {
            if nums[j] < nums[minIdx] {
                minIdx = j
            }
        }
        nums[i], nums[minIdx] = nums[minIdx], nums[i]
    }
    for i := 0; i < n-2; i++ {
        if 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 {
                res = append(res, []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--
            }
        }
    }
    return res
}
func main() {
    nums := []int{-1, 0, 1, 2, -1, -4}
    result := threeSum(nums)
    fmt.Println(result)
}

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

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

C [[-4, 2, 2], [-1, -1, 2]]

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

💡 Hint

Think about sorting the array first and then using two pointers to find pairs that sum with the current element to zero.

The function sorts the array and then uses a fixed pointer with two moving pointers to find triplets that sum to zero. It skips duplicates to ensure unique triplets. The output for the input [-1, 0, 1, 2, -1, -4] is [[-1, -1, 2], [-1, 0, 1]].

🧠 Conceptual

intermediate

Number of Unique Triplets in Three Sum

Given the input array [-2, 0, 1, 1, 2], how many unique triplets sum to zero?

A 2

B 1

C 3

D 0

💡 Hint

Try to find all sets of three numbers that add up to zero without repeating the same triplet.

The unique triplets are [-2, 0, 2] and [-2, 1, 1]. So there are 2 unique triplets.

🔧 Debug

advanced

Identify the Bug in Triplet Finding Code

What error will the following Go code produce when run, and why? func threeSum(nums []int) [][]int { var res [][]int n := len(nums) if n < 3 { return res } // Missing sorting step for i := 0; i < n-2; i++ { if 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 { res = append(res, []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-- } } } return res } func main() { nums := []int{-1, 0, 1, 2, -1, -4} result := threeSum(nums) fmt.Println(result) }

A The code will run correctly and output all unique triplets.

B The code will panic with an index out of range error due to left and right pointers.

C The code will not compile due to missing import of fmt package.

D The output is incorrect because the array is not sorted, so duplicates and sums are not handled properly.

💡 Hint

Sorting is essential for skipping duplicates and using two pointers correctly.

Without sorting, the two-pointer approach fails to find correct pairs and skip duplicates, resulting in incorrect output but no runtime error.

📝 Syntax

advanced

Identify Syntax Error in Three Sum Code

Which option contains a syntax error in the Go code snippet for three sum?

DSA Go

func threeSum(nums []int) [][]int {
    var res [][]int
    n := len(nums)
    if n < 3 {
        return res
    }
    sort.Ints(nums)
    for i := 0; i < n-2; i++ {
        if 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 {
                res = append(res, []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--
            }
        }
    }
    return res
}

A Missing import statement for "sort" package.

B Using := inside for loop initialization is invalid in Go.

C The for loop condition should use <= instead of <.

D The append function cannot be used with slices.

💡 Hint

Check if all used packages are imported.

The code uses sort.Ints but does not import the "sort" package, causing a compile-time error.

🚀 Application

expert

Optimizing Three Sum for Large Input

You have a very large array with millions of integers. Which approach is the best to optimize the Three Sum problem for unique triplets summing to zero?

A Use a brute force approach with recursion to generate all triplets.

B Use a hash set to store pairs and check for the third element in O(n^2) time but with extra space.

C Sort the array and use the two-pointer technique to find triplets in O(n^2) time.

D Use three nested loops to check all triplets in O(n^3) time.

💡 Hint

Consider time complexity and space usage for very large inputs.

Sorting and two-pointer approach gives O(n^2) time with no extra space, which is efficient for large inputs compared to other methods.

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