Solving the LeetCode "4Sum" Problem in Go

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

Introduction

The "4Sum" problem requires finding all unique quadruplets in an array that sum up to a given target. This problem extends the classic "Two Sum" and "3Sum" problems, making it a valuable exercise in mastering array manipulation and pointer techniques.

Problem Analysis

Given an array of integers, we need to find all distinct quadruplets (sets of four numbers) that add up to the target value. The solution must avoid duplicates and efficiently handle large input sizes. For example, with nums = [1,0,-1,0,-2,2] and target = 0, the output should include combinations like [-2,-1,1,2].

Solution Approach

The optimal approach involves sorting the array first and then using a combination of nested loops and two-pointer techniques. The steps are as follows:

1. Sort the array to enable efficient skipping of duplicates.
2. Use two nested loops to fix the first two numbers in the quadruplet.
3. Use two pointers (left and right) to find the remaining two numbers that complete the sum.
4. Skip duplicate values to ensure uniqueness in the results.

Go Implementation

package main
import (
"fmt"
"sort"
)
func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)
    n := len(nums)
    var result [][]int
    for i := 0; i < n-3; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        for j := i + 1; j < n-2; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }
            left := j + 1
            right := n - 1
            for left < right {
                sum := nums[i] + nums[j] + nums[left] + nums[right]
                if sum == target {
                    result = append(result, []int{nums[i], nums[j], 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 < target {
                    left++
                } else {
                    right--
                }
            }
        }
    }
    return result
}
func main() {
    nums1 := []int{1, 0, -1, 0, -2, 2}
    target1 := 0
    fmt.Println(fourSum(nums1, target1)) // Output: [[-2 -1 1 2] [-2 0 0 2] [-1 0 0 1]]
    nums2 := []int{2, 2, 2, 2, 2}
    target2 := 8
    fmt.Println(fourSum(nums2, target2)) // Output: [[2 2 2 2]]
}

Complexity Analysis

The time complexity is O(n³) due to the nested loops and two-pointer traversal. Sorting the array takes O(n log n), but the dominant factor is the nested loops. The space complexity is O(1) (excluding the output storage), as we only use a constant amount of extra space.

Testing and Examples

Key test cases include:

• Example 1: nums = [1,0,-1,0,-2,2], target = 0 → [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
• Example 2: nums = [2,2,2,2,2], target = 8 → [[2,2,2,2]]
• Edge Case: nums = [0,0,0,0], target = 0 → [[0,0,0,0]]

Best Practices and Tips

To optimize and avoid common pitfalls:

• Always sort the array first to simplify duplicate skipping.
• Use early termination conditions if the smallest sum exceeds the target.
• Skip duplicates efficiently by comparing adjacent elements in sorted order.
• Test edge cases like all zeros or large values to ensure robustness.