3Sum - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "3Sum" Problem in Go

Difficulty: Medium | Tags: Array, Two Pointers, Sorting

Introduction

The "3Sum" problem requires finding all unique triplets in an array that sum to zero. This problem is a classic example of using sorting and two-pointer techniques to efficiently solve a problem that would otherwise have a brute-force O(n³) complexity.

Problem Analysis

Given an array of integers, we need to find all triplets (i, j, k) where i ≠ j ≠ k and nums[i] + nums[j] + nums[k] = 0. The solution must avoid duplicate triplets. For example, in the array [-1, 0, 1, 2, -1, -4], the valid triplets are [-1, -1, 2] and [-1, 0, 1].

Solution Approach

The optimal approach involves sorting the array first, then using a combination of iteration and two-pointer technique. For each element, we treat it as the first element of the triplet and then use two pointers to find the remaining two elements that sum to zero. We skip duplicates to ensure unique triplets.

Go Implementation


package main
import (
"fmt"
"sort"
)
func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    var result [][]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 {
                result = append(result, []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 result
}
func main() {
    nums1 := []int{-1, 0, 1, 2, -1, -4}
    fmt.Println(threeSum(nums1)) // Output: [[-1 -1 2] [-1 0 1]]
    nums2 := []int{0, 1, 1}
    fmt.Println(threeSum(nums2)) // Output: []
    nums3 := []int{0, 0, 0}
    fmt.Println(threeSum(nums3)) // Output: [[0 0 0]]
}

Complexity Analysis

The time complexity is O(n²), where n is the number of elements in the array. Sorting the array takes O(n log n), and the two-pointer approach takes O(n²) in the worst case. The space complexity is O(1) or O(n) depending on the sorting algorithm used (in Go, sort.Ints uses O(log n) space for the sorting algorithm).

Testing and Examples

The provided test cases cover various scenarios, including arrays with multiple valid triplets, no valid triplets, and arrays with all zeros. Edge cases include arrays with exactly three elements and arrays with all negative or positive numbers.

Best Practices and Tips

Always sort the array first to leverage the two-pointer technique. Skip duplicate elements to avoid redundant triplets. Ensure the two-pointer logic correctly handles both moving pointers inward and skipping duplicates. Test edge cases thoroughly, including arrays with minimal length and extreme values.

Read more