## Thursday, December 1, 2022

### Easy_Question27 : 3Sum - Given an integer array nums, return all the triplets

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

``Two-pointer Technique``

`import java.util.*;public class FindTriplet {    List < List < Integer >> find3Numbers(int A[], int arr_size, int sum) {        List < List < Integer >> ans = new ArrayList < > ();        int l, r;        /* Sort the elements */        if (A == null || A.length < 3) {            return ans;        }        Arrays.sort(A);        /* Now fix the first element one by one and find the        other two elements */        for (int i = 0; i < arr_size - 2; i++) {            if (i > 0 && A[i] == A[i - 1])                continue;            // To find the other two elements, start two            // index variables from two corners of the array            // and move them toward each other            l = i + 1; // index of the first element in the            // remaining elements            r = arr_size - 1; // index of the last element            while (l < r) {                if (A[i] + A[l] + A[r] == sum) {                    ans.add(Arrays.asList(A[i], A[l], A[r]));                    l++;                    while (l < r && A[l] == A[l - 1]) {                        l++;                    }                    while (l < r && A[r] == A[r - 1]) {                        r--;                    }                }                 else if (A[i] + A[l] + A[r] < sum)                    l++;                else // A[i] + A[l] + A[r] > sum                    r--;            }        }        return ans;    }    // Driver program to test above functions    public static void main(String[] args) {        FindTriplet triplet = new FindTriplet();        int A[] = {-1,            0,            1,            2,            -1,            -4        };        int sum = 0;        int arr_size = A.length;        triplet.find3Numbers(A, arr_size, sum).forEach(System.out::println);    }}`
Complexity Analysis:
• Time complexity: O(N^2).
There are only two nested loops traversing the array, so time complexity is O(n^2). Two pointers algorithm takes O(n) time and the first element can be fixed using another nested traversal.
• Space Complexity: O(1).
As no extra space is required

## You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS