Solution For 3sum

The 3Sum problem on LeetCode is to find all unique triplets in the array which gives the sum of zero. In other words, the problem requires you to find three numbers from the array that sum up to zero.

The problem is quite popular and is considered a classic problem in computer science. The brute force approach to solve this problem would require three nested loops to check all possible triplets, which would take O(n^3) time complexity. Therefore, a more efficient solution should be used.

One way to solve this problem efficiently is by sorting the array first. Sorting the array would bring all the negative numbers to the left side of the array and all the positive numbers to the right side. The zero would end up in the middle.

Then, we can use a two-pointer approach to find the triplets. We start with fixing the first number and then look for the remaining two numbers whose sum adds up to the complement of the first number.

The two-pointer approach involves two pointers, one at the beginning and one at the end of the sorted array. We start by fixing the first number and then increment the left pointer if the sum of the first number and the left pointer element is less than the complement, or decrement the right pointer if the sum of the first number and the right pointer element is greater than the complement. If the sum is equal to the complement, we have found a triplet.

The code for the solution looks like this:

“`
class Solution {
public:
vector> threeSum(vector& nums) {
vector> result;
int n = nums.size();
sort(nums.begin(), nums.end());

    for (int i = 0; i < n - 2; i++) {
        if (i == 0 || nums[i] != nums[i-1]) {
            int l = i + 1, r = n - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    result.push_back({nums[i], nums[l], nums[r]});
                    while (l < r && nums[l] == nums[l+1]) l++;
                    while (l < r && nums[r] == nums[r-1]) r--;
                    l++;
                    r--;
                } else if (sum < 0) {
                    l++;
                } else {
                    r--;
                }
            }
        }
    }
    return result;
}

};
“`

The above code has a time complexity of O(n^2) and space complexity of O(1) as we are not using any extra space.

The vector result stores all unique triplets that sum up to zero. We sort the input array nums to bring all negative numbers to the left side and positive numbers to the right side. Then, we iterate through the array using a for loop, fixing the first number and then using the two-pointer approach to find the other two numbers.

The if statement inside the for loop is used to skip any duplicate values. The while loop inside the two-pointer approach is used to skip any duplicate values. Finally, the return statement returns the vector result containing all unique triplets that sum up to zero.

Step by Step Implementation For 3sum

public List 	> threeSum(int[] nums) {
    List 	> res = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i + 2 < nums.length; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {              // skip same result
            continue;
        }
        int j = i + 1, k = nums.length - 1;  
        int target = -nums[i];
        while (j < k) {
            if (nums[j] + nums[k] == target) {
                res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                j++;
                k--;
                while (j < k && nums[j] == nums[j - 1]) j++;  // skip same result
                while (j < k && nums[k] == nums[k + 1]) k--;  // skip same result
            } else if (nums[j] + nums[k] > target) {
                k--;
            } else {
                j++;
            }
        }
    }
    return res;
}

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

# Note:

# The solution set must not contain duplicate triplets.

# Example:

# Given array nums = [-1, 0, 1, 2, -1, -4],

# A solution set is:
# [
#   [-1, 0, 1],
#   [-1, -1, 2]
# ]
def threeSum(nums):
        res = []
        nums.sort()
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l, r = i+1, len(nums)-1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0:
                    l +=1 
                elif s > 0:
                    r -= 1
                else:
                    res.append((nums[i], nums[l], nums[r]))
                    while l < r and nums[l] == nums[l+1]:
                        l += 1
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    l += 1; r -= 1
        return res

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    
};

vector> threeSum(vector& nums) {
        // sort the array first
        sort(nums.begin(), nums.end());
        int n = nums.size();
        // result vector
        vector> res;
        // iterate over the array
        for (int i = 0; i < n; i++) {
            // if the current element is greater than 0, we can break as the rest of the array will also be greater than 0
            if (nums[i] > 0) {
                break;
            }
            // if the current element is the same as the previous element, we can skip it
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // two pointer approach, one at the beginning of the array and one at the end
            int j = i + 1;
            int k = n - 1;
            // target sum is 0 - current element
            int target = 0 - nums[i];
            // while the two pointers do not cross each other
            while (j < k) {
                // if the current sum is equal to the target sum
                if (nums[j] + nums[k] == target) {
                    // add the triplet to the result vector
                    res.push_back({nums[i], nums[j], nums[k]});
                    // move the left pointer to the next element
                    j++;
                    // move the right pointer to the previous element
                    k--;
                    // if the left pointer is at an element that is the same as the previous element, skip it
                    while (j < k && nums[j] == nums[j - 1]) {
                        j++;
                    }
                    // if the right pointer is at an element that is the same as the previous element, skip it
                    while (j < k && nums[k] == nums[k + 1]) {
                        k--;
                    }
                }
                // if the current sum is less than the target sum, move the left pointer to the next element
                else if (nums[j] + nums[k] < target) {
                    j++;
                }
                // if the current sum is greater than the target sum, move the right pointer to the previous element
                else {
                    k--;
                }
            }
        }
        // return the result vector
        return res;
    }

public class Solution {
    public IList> ThreeSum(int[] nums) {
            // sort the array
            Array.Sort(nums);
            List> res = new List>(); 
            
            for (int i = 0; i < nums.Length - 2; i++)
            {
                // if the current element is greater than 0, then there's no point
                // in considering it as the leftmost element since it can never sum to 0
                if (nums[i] > 0) break;
                
                // if the current element is the same as the previous element, then we've
                // already considered it as the leftmost element and can safely skip it
                if (i > 0 && nums[i] == nums[i - 1]) continue;
                
                int left = i + 1, right = nums.Length - 1, target = -nums[i];
                while (left < right)
                {
                    if (nums[left] + nums[right] == target)
                    {
                        res.Add(new List { nums[i], nums[left], nums[right] });
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    }
                    else if (nums[left] + nums[right] < target)
                    {
                        left++;
                    }
                    else
                    {
                        right--;
                    }
                }
            }
            
            return res;
        }
    }