Question

Leetcode link -> leetcode.com/problems/3sum/description

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: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.


Constraints:

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

Approach

Not the most efficient, can be improved further, will update this article once I find a better approach

1. Sort the array:
2. Sorting simplifies the process of finding triplets and makes it easy to avoid duplicates.

3. Example: [-1, 0, 1, 2, -1, -4] becomes [-4, -1, -1, 0, 1, 2].

4. Iterate through each number:

5. For each number nums[i], use two pointers (left and right) to find two other numbers that sum to zero with nums[i].

6. Two-pointer technique:

7. left starts just after i and right starts at the end of the array.
8. If the sum of nums[i] + nums[left] + nums[right] equals zero, store the triplet and move both pointers while skipping duplicates.
9. If the sum is less than zero, increment left to increase the sum.

10. If the sum is greater than zero, decrement right to decrease the sum.

11. Avoid duplicates:

12. Skip duplicate values of i, left, and right to ensure unique triplets are added to the result list.

Complexity

Time

𝑂( 𝑛² )

• Sorting the array takes O(n log n).
• The main loop runs in O(n²) because for each element, the two-pointer scan is linear.
• Overall O(n²)

Space

𝑂(𝑛)

• Due to the space required for sorting.

Code

from typing import List
from collections import defaultdict


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()  # Step 1: Sort the array
        res = []

        for i in range(len(nums) - 2):
            # Step 2: Skip duplicates for the current number
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left, right = i + 1, len(nums) - 1

            while left < right:
                total = nums[i] + nums[left] + nums[right]

                if total == 0:
                    res.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1

                    # Step 3: Skip duplicates for the second and third numbers
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1

                elif total < 0:
                    left += 1
                else:
                    right -= 1

        return res