0015. 3Sum

leetcode

Problem:

Find all unique triplets in the array which gives the sum of zero. The solution set must not contain duplicate triplets.

Solution Description:

To implement a solution for the 3Sum problem, we need to:

Sort the array to enable the two-pointer approach for finding triplets.
Iterate through the array with the first pointer, and for each element, use two additional pointers (one starting just after the first pointer, and the other starting from the end of the array) to find pairs that sum up to the negative value of the current element.
If the sum of the triplet (current element and the values pointed by the two pointers) is zero, then it's a valid triplet.
Move the pointers closer to skip duplicate elements and continue the search.
Continue the iteration until all triplets are found.
Return the list of unique triplets.

Note:-

Time Complexity: O(n²) â Sorting the array takes O(n log n) time and the two-pointer strategy takes O(n) time for each element, resulting in O(n²) overall. Space Complexity: O(1) â aside from the space required for the output list, the solution uses a constant amount of space.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [[-1, 0, 1], [-1, -1, 2]] The algorithm starts by sorting the array: [-4, -1, -1, 0, 1, 2]

For the first element (-4), the remaining array is [-1, -1, 0, 1, 2]
- Using two pointers, we don't find any triplet that sums to zero
For the second element (-1), the remaining array is [-1, 0, 1, 2]
- We find triplets: [-1, -1, 2] and [-1, 0, 1]

Setup:

Here is the general framework in which we will plug our code blocks. We will use modern JavaScript and include a testing setup to verify our solution.

// Helper definitions to setup logging for testing.

/**
 * Main function to find all unique triplets in the array that sum to zero.
 * @param {number[]} nums
 * @returns {number[][]} - Array of arrays containing unique triplets
 */
function threeSum(nums) {
    const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
    const table = typeof NestedInteger !== 'undefined' ? () => {} : console.table;

    nums = nums.sort((a, b) => a - b);

    log("A", JSON.stringify(nums));

    if (nums.length < 3) return [];
    if (nums[0] === 0 && nums[0] === nums[nums.length - 1]) return [[0, 0, 0]];

    const result = [];

    for (let i = 0; i < nums.length - 2; i += 1) {
        // Skip duplicates for the current element
        if (i > 0 && nums[i] === nums[i - 1]) continue;

        const a = nums[i];
        let j = i + 1;
        let k = nums.length - 1;

        while (j < k) {
            const b = nums[j];
            const c = nums[k];
            const tsum = a + b + c;

            log('c', `i = ${i}; j = ${j}; k = ${k}`);
            log('d', `a = ${a}; b = ${b}; c = ${c}`);
            log('e', `tsum = ${tsum}`);

            if (tsum === 0) {
                result.push([a, b, c]);

                while (j < k && nums[j] === b) j += 1;
                while (j < k && nums[k] === c) k -= 1;
            } else if (tsum < 0) {
                j += 1;
            } else {
                k -= 1;
            }
            log('=======');
        }
    }

    return result;
}

// Test cases to validate our solution.
const testCases = [
    { nums: [3,0,-2,-1,1,2], expected: [[-2,-1,3],[-2,0,2],[-1,0,1]] },
    { nums: [-1, 0, 1, 2, -1, -4], expected: [[-1, 0, 1], [-1, -1, 2]] },
    { nums: [], expected: [] },
    { nums: [0], expected: [] },
    { nums: [0, 0, 0], expected: [[0, 0, 0]] },
    { nums: [-2, 0, 0, 2, 2], expected: [[-2, 0, 2]] },
    // Additional edge case where we have multiple triplet combinations
    { nums: [-4, -1, -1, 0, 1, 2], expected: [[-1, -1, 2], [-1, 0, 1]] }
];

// Execute the test cases to verify the solution.
testCases.forEach((test, index) => {
    const result = threeSum(test.nums);
    console.log(`Test Case ${index + 1}: ${JSON.stringify(result) === JSON.stringify(test.expected) ? 'Passed' : 'Failed'} (Expected: ${JSON.stringify(test.expected)}, Got: ${JSON.stringify(result)})`);
});