The problem

Aight, back to difficult problems.

I need to find all collections of three digits in a collection that sum to zero.

I feel like the first thing to do is sort the array - O(N logn) time - because we are trying to target a specific number - 0 - and if we sort we have the opportunity to eliminate entire areas of the area, or at least know which direction to searching from.

I'm still fuzzy on the solution, especially on how we'll ensure we're avoiding duplicate combinations. One way would be to store these found groups in a Set to avoid the duplicates, but I think in that case we'd need sort the arrays so they're seen as duplicates? But also as we learned in a previous problem, Sets store objects by reference, so two arrays might have the same internal values, but not be counted as duplicates as they point to different places in memory.

Okay, so fast forward, and I've gotten the solution and understand the algorithm. It's essentially a two pointer solution with an extra step - a 3 pointer solution if you will - and runs in O(n^2) time.

The solution

As I mentioned above, the first step is to sort the array. From there, we use a for loop to iterate forward through the array, stopping when the value we're on is greater than zero. The sorted array affords us this. We're trying to find three values that sum to zero, and if the lowest value is greater than zero, it's impossible to sum to zero. From there, we use two pointers, one immediately to the left of our iterator and one all the way at the end of the array, and progressively march inward until we find three values that sum to zero. If the triplet sum is less than zero, we march the left side forward, else we march the right side down, moving the sum potentially higher and lower, respectively.

Since we need to avoid duplicates, we continue through our for loop if the current iterator value is the same as the previous. When we find a triplicate match, we march left and right inward until both are new values, since any triplicate with the same index, left or right would require the same third value and therefore be a duplicate of what we already found.

function threeSum(nums: number[]): number[][] {
    const results = []
    nums.sort((a,b) => a-b)
    
    for(let i = 0; i < nums.length - 2; i++){
        if(i > 0 && nums[i] === nums[i-1]) continue; 
        if(nums[i] > 0) break; 
        
        let left = i + 1;
        let right = nums.length - 1;
        
        while(left < right){
            const sum = nums[i] + nums[left] + nums[right];
            
            if(sum === 0){
                results.push([nums[i], nums[left], nums[right]])
                
                while(left < right && nums[left] === nums[left + 1]) left++;
                while(left < right && nums[right] === nums[right - 1]) right--;
                
                left++;
                right--;
            } else if(sum > 0){
                right--; 
            } else {
                left++;
            }
        }
    }
    return results;
};

Parting thoughts

I used Claude to properly understand the algorithm. It definitely took a while for it to click, but I feel confident that I'm able to explain it. If I wanted to do 4-sum, it would essentially be the same algorithm with an additional nested for loop.

On the next one!