3Sum

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

 class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums.length < 3) return new ArrayList<>();
        Arrays.sort(nums);
        Set<List<Integer>> triplet= new HashSet<>();
        for (int i = 0; i < nums.length - 2; i++) {
            int j = i + 1;
            int k = nums.length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) triplet.add(Arrays.asList(nums[i], nums[j++], nums[k--]));
                else if (sum > 0) k--;
                else if (sum < 0) j++;
            }
        }

        return new ArrayList<>(triplet);
    }
}

Try it on Leetcode

Here, we are going to solve using three variables iteratively. j iterates from beginning and k iterates from end. If array length is less than 3, then return a new arraylist. Below are steps to be followed.,

1) Sort the array.

2) Create a set with list of integer as a type. Our overall return type must be List<List> but reason behind to use Set is to avoid duplicates of triplets.

3) For each i,

 a) j is i+1, k is nums.length-1

 b) sum variable is overall sum of nums[i], nums[j], nums[k].

 c) If sum is equal to 0, then add those triplets(nums of i, j, k) to triplet set as a list.

 d) Else if sum less than 0, increment j by 1,

 e) Else if sum greater than 0, decrement k by 1.

 f) Repeat above all from step 3, until i reaches length - 2(i.e. to find last triplet)

4) Finally return triplet set in a new arraylist.

Below is sample working given for one iteration

nums - [-1,0,1,2,-1,-4]
sorted - [-4,-1,-1,0,1,2]
n = 6

Loop for: i = 0
j = 1, k = 5
sum = -4  + -1 + 2 = -3 < 0 ,  j++

j = 2, k = 5
sum = -4  + -1 + 2 = -3 < 0 , j++

 j = 3, k = 5
sum = -4  + 0 + 2 = -2 < 0, j++

 j = 4, k = 5
sum = -4  + 1 + 2 = -1 < 0 , j++

Like this iteration will goes on...

Related Post:

Click here for July month challenges with solution and explanation

Click here for June month challenges with solution and explanation

Click here for May month challenges with solution and explanation

Click here for April month challenges with solution and explanation

Click Follow button to receive latest updates from us instantly.

Please let us know about your views in comment section.

Help Others, Please Share..!!!!

                                                     😍..Happy Coding...😍