3Sum

main.md

Question

Approach

1. I created a map to store number combinations that sum up to 0.
2. loop through the numbers but i stop early since im adding 3 numbers and dont want to go out of bounds.
3. pointers are assigned to track the numbers being addded.
4. if a set of numbers that are equal to 0, do not exist in tha mapthe numbers are added to the result array.

Complexity

• Time complexity:O(N^2)

• Space complexity:O(N)

Code

function threeSum(nums: number[]): number[][] {
    nums.sort((a, b) => a - b);

    const result: number[][] = [];
    const seen = new Map<string, boolean>();

    for (let i = 0; i < nums.length - 2; i++) {
        let left = i + 1;
        let right = nums.length - 1;

        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];

            if (sum === 0) {
                const triplet = [nums[i], nums[left], nums[right]];
                const key = triplet.join(",");
                
                if (!seen.has(key)) {
                    seen.set(key, true);
                    result.push(triplet);
                }

                left++;
                right--;
            } 
            else if (sum < 0) {
                left++;
            } 
            else {
                right--;
            }
        }
    }

    return result;
}