15. 3Sum

Intuition

The problem requires finding all unique triplets in the array that sum up to zero. The key observation is that sorting the array helps in efficiently finding these triplets using a two-pointer approach. Sorting ensures that we can avoid duplicates easily and systematically move towards the solution.

Approach

1. Sort the Array: Sort the input array nums in non-decreasing order. This helps in handling duplicates and efficiently using the two-pointer technique.
2. Iterate Through the Array: Use a for loop to iterate through the array: - For each element, set it as the first element of the triplet. - Initialize two pointers: left just after the current element and right at the end of the array. - Use a while loop to move the pointers towards each other: - Calculate the sum of the three elements: the current element, the element at the left pointer, and the element at the right pointer. - If the sum is zero, add the triplet to the result list and move both pointers inward, skipping duplicate elements. - If the sum is greater than zero, move the right pointer left to reduce the sum. - If the sum is less than zero, move the left pointer right to increase the sum. - Skip duplicate elements for the current element to avoid duplicate triplets.
3. Return the Result: After iterating through the array, return the result list containing all unique triplets.

Complexity

Time Complexity:

O(n^2), where n is the length of the array. Sorting the array takes O(n log n), and the two-pointer technique for each element takes O(n), resulting in an overall time complexity of O(n^2).

Space Complexity:

O(n), as the result list stores all the unique triplets. Sorting the array in-place uses O(1) additional space, and the set used for avoiding duplicates is not needed since the array is sorted.

Code

C++

#include 
#include 
#include 
using namespace std;
class Solution {
public:
    vector> threeSum(vector& nums) {
        sort(nums.begin(), nums.end());
        set> uniqueTriplets;
        vector> result;
        for (int i = 0; i < nums.size(); ++i) {
            int left = i + 1;
            int right = nums.size() - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    uniqueTriplets.insert({nums[i], nums[left], nums[right]});
                    ++left;
                    --right;
                } else if (sum > 0) {
                    --right;
                } else {
                    ++left;}}}
        for (const auto& triplet : uniqueTriplets) {
            result.push_back(triplet);
        }
        return result;
    }};

Python

from typing import List
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        unique_triplets = set()
        result = []
        for i in range(len(nums)):
            left, right = i + 1, len(nums) - 1
            while left < right:
                sum = nums[i] + nums[left] + nums[right]
                if sum == 0:
                    unique_triplets.add((nums[i], nums[left], nums[right]))
                    left += 1
                    right -= 1
                elif sum > 0:
                    right -= 1
                else:
                    left += 1
        for triplet in unique_triplets:
            result.append(list(triplet))
        return result

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
class Solution {
    public List> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set> uniqueTriplets = new HashSet<>();
        List> result = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    uniqueTriplets.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    ++left;
                    --right;
                } else if (sum > 0) {
                    --right;
                } else {
                    ++left;
                }}}
        result.addAll(uniqueTriplets);
        return result;}}

JavaScript

var threeSum = function(nums) {
    nums.sort((a, b) => a - b);
    let st= new Set ();
    for (i=0;i 0 )
       right--;
      else {
left++;
      }}}
    return Array.from(st).map((el)=>JSON.parse(el))

};