3Sum

Given an array of integers, find all unique triplets that sum to zero.

Approach

The strategy involves sorting the input array first to efficiently handle duplicate triplets and to use the two-pointer technique. A fixed pointer iterates through the array. For each fixed element, two pointers (left and right) are initialized to scan the rest of the array. If the sum of the fixed element and the elements at the left and right pointers is zero, the triplet is added to the result. If the sum is greater than zero, the right pointer is moved inwards; otherwise, the left pointer is moved inwards. Duplicate triplets are avoided by skipping over consecutive identical elements for both the fixed pointer and the left pointer. If the fixed element becomes positive, we can stop early because the sorted array will only contain larger numbers, making a sum of zero impossible.

Solution

1. This was the famous 3-sum problem, it was a bit tough, specially skipping negatives.
2. we are taking one fixed pointer from o to n-2 len, we have left which is fixed +1 and right at last element (one fixed element and 2 pointer method).
3. sort the array before we began, if sum of all 3 pos is > 0 right -- if < 0 then left ++, else append those triplet to ans and dec right and inc left.
4. to avoid duplicates, the top loop if fixed pos > 0 and the prev fixed int is same as present one, skip it to not add those values again.
(for eg:- [-1, -1, 0, 1]. shld be -1, 0, 1 so skip if the prev value is same in cases such as this).
4.1 a second while loop to skip the duplicated for [1,2,0,1,0,0,0,0], if left is same as prev value and is less than right skip that left by inc the left.
4.2 if the smallest value it is fixed greater than 0 then no way the sum is o break and return the value.
5. return the ans.

time comp:- o(n^2)
space comp:- o(1)
"""
class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        ans = []
        n = len(nums)

        nums.sort()
        for fixed in range(n - 2):

            if nums[fixed] > 0:
                break
            
            if fixed > 0 and nums[fixed - 1] == nums[fixed]:
                continue
            left = fixed + 1
            right = n - 1

            while left < right:
                curr_sum = nums[fixed] + nums[left] + nums[right]
                if curr_sum == 0:
                    ans.append([nums[fixed], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left-1]:
                        left += 1
                elif curr_sum > 0:
                    right -= 1
                else:
                    left += 1

        return ans

Complexity

• Time: O(n^2) — Sorting takes O(n log n), and the nested loop with two pointers takes O(n^2).
• Space: O(1) — Ignoring the space for the output, as the sorting is done in-place.