15 3Sum

This is a problem where we need to use the knowledge of 2Sum and 2Sum II. We are required to find triplets whose sum equals to $0.$ We can’t have duplicate triplets and use the same element multiple times.

1. Sort the array increasingly
2. Iterate over the array and consider one element at a time.
		2.1. From here, we can use the logic of two sum by the two pointers technique.
		2.2. Check if (nums[i] + nums[L] + nums[R]) equals 0.
			2.2.1. If yes, add to result

Code:

Java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
 
        Arrays.sort(nums);
 
        for (int i=0;i<nums.length;++i) {
            if (i > 0 && nums[i]==nums[i-1]) continue;
 
            int curr = nums[i];
 
            int L=i+1;
						int R=nums.length-1;
            while(L<R) {
                
                int sum = nums[L]+nums[R]+curr;
                if (sum == 0) {
                    res.add(Arrays.asList(curr,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) R--;
                else if(sum<0) L++;
            }
        }
        return res;
    }
}

Big O Analysis

• Runtime

  The runtime complexity here is $O(N^2)$ since we have one for loop and a while loop nested in it.

• Memory

  The memory usage is O(1) since we are not using any extra datastructure.

— A

GitHub | Twitter