NUHMAN.com

Introduction

LeetCode 15: 3Sum is a classic problem that tests your ability to find unique triplets in an array that sum up to zero. It's a twist on the two-sum problem, expanded to three numbers.

In this article, we’ll explore the optimal sorting + two pointers technique and write a clean solution in Go (Golang).

Problem Statement

Given an integer array nums, return all the unique triplets [nums[i], nums[j], nums[k]] such that:

nginx

i ≠ j, i ≠ k, j ≠ k
nums[i] + nums[j] + nums[k] == 0

Note: The solution set must not contain duplicate triplets.

Examples

go

Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
go

Input: nums = [0, 1, 1]
Output: []
go

Input: nums = [0, 0, 0]
Output: [[0, 0, 0]]

Approach: Sorting + Two Pointers

1. Sort the array.
2. Loop through each number i, and for each, use two pointers (left and right) to find two more numbers such that the sum is zero.
3. Skip duplicates to avoid repeated triplets.

Why it works:

Sorting helps:

• Easily skip duplicates.
• Use the two-pointer approach for the remaining part of the array efficiently.

Go Implementation

go

package main

import (
    "fmt"
    "sort"
)

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    result := [][]int{}

    for i := 0; i < len(nums)-2; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue // skip duplicate i
        }

        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]})

                // Skip duplicates for left and 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() {
    testCases := [][]int{
        {-1, 0, 1, 2, -1, -4},
        {0, 1, 1},
        {0, 0, 0, 0},
        {-2, 0, 1, 1, 2},
    }

    for _, nums := range testCases {
        fmt.Printf("Input: %v -> Triplets: %v\n", nums, threeSum(nums))
    }
}

Step-by-Step Example: [-1, 0, 1, 2, -1, -4]

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

• i = 0 (nums[i] = -4), no zero-sum found
• i = 1 (nums[i] = -1)
• left = 2 (nums[left] = -1), right = 5 (nums[right] = 2)
• sum = -1 -1 + 2 = 0 → ✅
• Add [-1, -1, 2], skip duplicates
• Continue checking for more
• i = 2 (skip, duplicate of -1)

Result: [[-1, -1, 2], [-1, 0, 1]]

Time and Space Complexity

• Time Complexity: O(n²)
• Outer loop: O(n)
• Inner two-pointer search: O(n)
• Space Complexity: O(1) (excluding result list)

Key Takeaways

• Sorting simplifies the logic and helps avoid duplicates.
• Two pointers reduce time complexity from O(n³) to O(n²).
• Always handle edge cases like duplicates, empty arrays, and all zeros.