3Sum

Problem Statement

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].

Approach: Sort & Two Pointers

A brute force approach involves three nested loops, which gives a terrible $O(n^3)$ time complexity. We can improve this significantly to $O(n^2)$ by applying the Two Pointers technique.

To do this, we must sort the array first. Sorting serves two crucial purposes:

1. It allows us to use the Two Pointers technique to find the remaining two numbers (exactly like in Two Sum II).
2. It groups identical numbers together, making it incredibly easy to skip duplicates and avoid returning duplicate triplets.

The idea is to iterate through the sorted array. For each number nums[i], we treat it as our first number. We then use a left pointer starting at i + 1 and a right pointer starting at the end of the array to find two numbers that sum up to -nums[i].

1. Sort the input array nums in ascending order.
2. Initialize an empty array result to hold the triplets.
3. Iterate through nums using a standard for loop with index i.
   • Optimization: If nums[i] > 0, break the loop. Since the array is sorted, all subsequent numbers will also be positive, making it impossible to sum to zero.
   • Skip Duplicates: If i > 0 and nums[i] === nums[i - 1], continue to skip the duplicate element and avoid duplicate triplets.
4. Initialize left = i + 1 and right = nums.length - 1.
5. Start a while loop that runs as long as left < right:
   • Calculate sum = nums[i] + nums[left] + nums[right].
   • If sum === 0, we found a valid triplet! Push [nums[i], nums[left], nums[right]] to result.
     • Increment left and decrement right to look for the next potential pair.
     • Skip Duplicates for Left Pointer: Use a while loop to keep incrementing left as long as nums[left] === nums[left - 1] and left < right.
   • If sum > 0, the sum is too large, so we decrement right.
   • If sum < 0, the sum is too small, so we increment left.
6. Return result.

Solution

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function threeSum(nums) {
    // 1. Sort the array to use two pointers and easily skip duplicates
    nums.sort((a, b) => a - b);
    const result = [];
    
    // 2. Iterate to fix the first number
    for (let i = 0; i < nums.length - 2; i++) {
        // Optimization: if the smallest number is > 0, we can never sum to 0
        if (nums[i] > 0) break;
        
        // Skip duplicate values for the first number
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        
        // 3. Two Pointers to find the remaining two numbers
        let left = i + 1;
        let right = nums.length - 1;
        
        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];
            
            if (sum === 0) {
                result.push([nums[i], nums[left], nums[right]]);
                
                left++;
                right--;
                
                // Skip duplicate values for the left pointer
                while (left < right && nums[left] === nums[left - 1]) {
                    left++;
                }
            } else if (sum > 0) {
                right--;
            } else {
                left++;
            }
        }
    }
    
    return result;
}

Complexity Analysis

• Time Complexity: $O(n^2)$ where $n$ is the length of the array. Sorting the array takes $O(n \log n)$ time. The outer for loop runs $O(n)$ times, and for each iteration, the inner while loop (Two Pointers) takes $O(n)$ time. The dominant term is $O(n^2)$.
• Space Complexity: $O(1)$ auxiliary space (or $O(n)$ depending on the sorting algorithm implementation). We do not use any extra space that scales with the input size other than the output array, which is usually not counted towards space complexity.