3Sum medium

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 1

Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: Because [-1 + (-1) + 2 = 0] and [-1 + 0 + 1 = 0]

Example 2

Input: nums = [0,1,1] Output: [] Explanation: Because no triplet sum to zero.

Steps

1. Sort the array: Sorting allows us to efficiently skip duplicate numbers and use a two-pointer approach.
2. Iterate through the array: The outer loop iterates through each number in the sorted array.
3. Two-pointer approach: For each number, we use two pointers, left and right, to find a pair that sums to the negative of the current number.
4. Handle duplicates: We skip duplicate numbers to avoid duplicate triplets in the result.
5. Store the triplets: If a triplet summing to zero is found, it's added to the result.

Explanation

The core idea is to leverage sorting to optimize the search for triplets. After sorting, we can efficiently use the two-pointer technique to find pairs that sum to a target (the negative of the current number in the outer loop). Skipping duplicate numbers prevents redundant triplets from being included in the output.

The time complexity is dominated by the sorting step, which is O(n log n). The nested loops appear to be O(n^2), but because of the way we skip duplicates and the two-pointer approach, the overall complexity remains O(n^2) in the worst case. The space complexity is O(1) if we ignore the space used for the result (which depends on the number of triplets found), otherwise it's O(m) where m is the number of triplets.

Code

function threeSum(nums: number[]): number[][] {
    const result: number[][] = [];
    nums.sort((a, b) => a - b); // Sort the array

    for (let i = 0; i < nums.length - 2; i++) {
        // Skip duplicate numbers
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }

        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]]);

                // Skip duplicate numbers
                while (left < right && nums[left] === nums[left + 1]) {
                    left++;
                }
                while (left < right && nums[right] === nums[right - 1]) {
                    right--;
                }

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

    return result;
}

Complexity

• Time Complexity: O(n^2), dominated by the nested loops after sorting. The sorting step itself is O(n log n).
• Space Complexity: O(m) where m is the number of triplets found (to store the result). If we disregard the output array's space, it's O(1).