Learning Journal

2/27/2024

3sum

function threeSum(nums: number[]): number[][] {
   
   const results:number[][] = [];

   nums.sort();

   for(let i = 0; i < nums.length - 1; i++) {
       if(i !== 0 && nums[i] === nums[i - 1])
            continue;

        const numI = nums[i];
        
        const numKSeen = new Map<number, boolean>(); 

        for(let j = i + 1; j < nums.length; j++){
            const numJ = nums[j];            
            
            if(numKSeen.has(-numI - numJ)){
                results.push([numI, numJ, -numI - numJ]);
                
                while(j < nums.length - 1 && nums[j] === nums[j + 1])
                  j++;
            }
            numKSeen.set(numJ, true);
            
        }
   } 

   return results;
};function threeSum(nums: number[]): number[][] {
   
   const results:number[][] = [];

   nums.sort();

   for(let i = 0; i < nums.length - 1; i++) {
       if(i !== 0 && nums[i] === nums[i - 1])
            continue;

        const numI = nums[i];
        
        const numKSeen = new Map<number, boolean>(); 

        for(let j = i + 1; j < nums.length; j++){
            const numJ = nums[j];            
            
            if(numKSeen.has(-numI - numJ)){
                results.push([numI, numJ, -numI - numJ]);
                
                while(j < nums.length - 1 && nums[j] === nums[j + 1])
                  j++;
            }
            numKSeen.set(numJ, true);
            
        }
   } 

   return results;
};

THE PROBLEM

There are 2 approaches for this problem: hash table and 2 pointers. However, I like the hash table approach more because it's more intuitive.

Basically, you have 3 pointers: i, j, and k.

Pointer i starts from 0 to the second to last elements. For each iteration of i, you set j from the element next to i and let it go to the last element. You also have a basket to keep track of "k" elements. In the first iteration, the basket is empty, because we only check 2 first elements. Then, when j moves away from i, we mark the element that j goes through to be k and the current element that j point to be j. This clever setting let us not to goes through the array multiple time. Each time, we check if those 3 elements add to 0, it they do, add them to the results array.

Revised by ChatGPT

This problem can be approached using either a hash table or the two-pointer method. I prefer the hash table approach for its intuitiveness.

The algorithm involves three pointers: i, j, and k.

Pointer i iterates from the beginning of the array up to the second-to-last element.
For each iteration of i, pointer j starts from the element next to i and moves towards the end of the array.
We maintain a hash table (referred to as a "basket") to keep track of potential k elements. Initially, the basket is empty because we only consider the first two elements. As j moves forward, we mark the element at the previous position of j as k and the current element as j.
This setup allows us to avoid multiple passes through the array. We check if the sum of the elements at i, j, and k is zero. If it is, we add the triplet to the results array.

This approach efficiently finds all unique triplets in the array that sum to zero.