15. 3Sum

INFO

Problem: 3Sum

Pattern: Sorting / two pointers / duplicate skipping

3Sum asks for all unique triplets whose sum is zero. The main challenge is not just finding triplets; it is avoiding duplicate answers.

Sorting the array gives us two advantages. First, duplicates become adjacent, so they are easier to skip. Second, once we fix one value, we can use two pointers to search the remaining range for the two values that complete the sum.

Approach

Sort the array. Then iterate through each value as the first number in the triplet. For every fixed value:

1. Skip it if it is the same as the previous fixed value.
2. Set a left pointer just after the fixed index.
3. Set a right pointer at the end of the array.
4. Add the three numbers.
5. If the sum is too small, move the left pointer right.
6. If the sum is too large, move the right pointer left.
7. If the sum is zero, store the triplet and skip duplicate left values.

This works because the sorted array tells us which direction to move. A smaller sum needs a larger left value. A larger sum needs a smaller right value.

Swift Notes

The implementation uses nums.sorted() so the original input remains unchanged. The result is an array of integer arrays: [[Int]]. After finding a valid triplet, the left pointer moves forward and skips repeated values to avoid returning the same triplet again.

Complexity

• Time complexity: O(n^2). Sorting costs O(n log n), but the nested fixed-index and two-pointer scan dominates.
• Space complexity: O(n) or O(log n) depending on sorting implementation details, plus the output array.

Edge Cases

• Multiple zeros, such as [0, 0, 0], should return one triplet.
• Duplicate negative or positive values should not create duplicate triplets.
• Arrays with fewer than three values cannot produce a triplet.

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        let sortedNums = nums.sorted()
        var result: [[Int]] = []
        for (index, val) in sortedNums.enumerated() {
            if index > 0 && val == sortedNums[index - 1] {
                continue
            }
            var k = index + 1
            var j = sortedNums.count - 1
            while k < j {
                let threeSum = val + sortedNums[k] + sortedNums[j]
                if threeSum > 0 {
                    j -= 1
                } else if threeSum < 0 {
                    k += 1
                } else {
                    result.append([val, sortedNums[k], sortedNums[j]])
                    k += 1
                    while sortedNums[k] == sortedNums[k - 1] && k < j {
                        k += 1
                    }
                }
            }
        }
        return result
    }
}

var solution = Solution()

var testcase1 = solution.threeSum([-1,0,1,2,-1,-4])
print(testcase1) // [[-1,-1,2],[-1,0,1]]

var testcase2 = solution.threeSum([0,1,1])
print(testcase2) // []

var testcase3 = solution.threeSum([0,0,0])
print(testcase3) // [[0,0,0]]