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